結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
|
提出日時 | 2016-04-02 12:46:22 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 1,034 bytes |
コンパイル時間 | 558 ms |
コンパイル使用メモリ | 55,460 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-02 10:01:06 |
合計ジャッジ時間 | 1,235 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include<iostream>#include<cstring>using namespace std;const int NODE = 14;const int BUF = 1 << NODE;int nNode;int adj[NODE][NODE];void read() {memset(adj, 0, sizeof(adj));int nEdge;cin >> nNode >> nEdge;for (int i = 0; i < nEdge; ++i) {int s, t, c;cin >> s >> t >> c;adj[s][t] = c;}}int rec(int mask, int dp[BUF]) {if (mask == 1 << nNode) {return 0;}int &ret = dp[mask];if (ret >= 0) return ret;ret = 0;for (int i = 0; i < nNode; ++i) {if (mask & (1 << i)) continue;int toAdd = 0;for (int j = 0; j < nNode; ++j) {if ((mask & (1 << j))) {toAdd += adj[j][i];}}ret = max(ret, rec(mask | (1 << i), dp) + toAdd);}return ret;}void work() {int dp[BUF];memset(dp, -1, sizeof(dp));cout << rec(0, dp) << endl;}int main() {read();work();return 0;}