結果

問題 No.357 品物の並び替え (Middle)
ユーザー Hachimori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0