結果
問題 | No.845 最長の切符 |
ユーザー |
![]() |
提出日時 | 2019-06-28 22:53:38 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,096 bytes |
コンパイル時間 | 1,019 ms |
コンパイル使用メモリ | 29,952 KB |
実行使用メモリ | 18,296 KB |
最終ジャッジ日時 | 2024-07-02 05:03:47 |
合計ジャッジ時間 | 3,309 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 15 RE * 5 |
ソースコード
#include <stdio.h>#define max(X, Y) ((X) > (Y) ? (X) : (Y))typedef long long ll;//struct edge {ll cost, ll to; };const ll INF = 1ll << 60ll;const ll MINF = -1 * (1ll << 60ll);ll dp[1 << 16][32];ll n, m;ll graph[32][32];ll a, b, c;ll ans;ll dfs(ll pos, ll s);int main(){scanf("%lld %lld", &n, &m);for (int i = 0; i < m; i++) {scanf("%lld %lld %lld", &a, &b, &c);graph[a][b] = graph[b][a] = c;}for (int i = 1; i <= n; i++) {for (int i = 1 << n; i >= 0; i--) {for (int j = 1; j <= n; j++) {dp[i][j] = 0;}}ans = max(ans, dfs(i, 1 << i));}printf("%lld\n", ans);}ll dfs(ll pos, ll s){if (dp[s][pos] ) {return dp[s][pos];}ll ret = 0;for (int i = 1; i <= n; i++) {if (graph[pos][i]) {ll to = i;ll cost = graph[pos][i];if (!(s & (1 << to))) {ret = max(ret, dfs(to, s | (1 << to)) + cost);}}}return dp[s][pos] = ret;}