結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2024-06-23 22:13:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 736 bytes |
コンパイル時間 | 2,164 ms |
コンパイル使用メモリ | 196,892 KB |
最終ジャッジ日時 | 2025-02-22 00:17:11 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include<bits/stdc++.h>using namespace std;const long long inf=1e17;int A[21];int dp[1 << 21];int main(void){long long n,m;cin >> n >> m;vector<vector<int>> a(n,vector<int>(n,0));for(int i=0;i<m;i++){int u,v,c;cin >> u >> v >> c;a[u][v] = c;}dp[0]=0;// 1は選択済み。0はこれからfor(int msk=0; msk<(1<<n); msk++){for(int j=0; j<n; j++){if(!(msk & (1<<j))){//まだ選択してないint total = 0;for(int i=0;i<n;i++){if(msk & (1<<i)) total += a[j][i];}dp[msk+(1<<j)]= max(dp[msk+(1<<j)],dp[msk]+total);}}}cout << dp[(1<<n)-1] << endl;return 0;}