結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2022-12-22 21:59:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,511 bytes |
コンパイル時間 | 1,807 ms |
コンパイル使用メモリ | 200,200 KB |
最終ジャッジ日時 | 2025-02-09 18:26:01 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(),(a).rend()#define PRINT(a) cout << (a) << endl#define pb push_back#define eb emplace_back#define mp make_pair#define Fi first#define Se second#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';using ll = long long int;using P = pair<int,int>;using vi = vector<int>;using vvi = vector<vi>;using vvvi = vector<vvi>;using pii = pair<int, int>;template <typename T> using PQ = priority_queue<T>;template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }const int INF = 1001001001;const ll LINF = 1001001001001001001ll;const int MOD = 1e9 + 7;int main(){int n,m;cin >> n >> m;vector score(n, vector<P>());REP(i,m){int u, v, s;cin >> u >> v >> s;score[u].emplace_back(P(v,s));}int S = 1<<n;vi dp(S,-1);dp[0] = 0;auto sc = [&](int x, int s){int ret=0;for(auto [v, w] : score[x]){if( (s >> v) & 1)ret += w;}return ret;};REP(s, S){if(dp[s]==-1)continue;REP(i, n){if( (~s >> i) & 1){chmax(dp[s | (1<<i)], dp[s] + sc(i, s));}}}cout << dp[S-1] << endl;}