結果
問題 | No.845 最長の切符 |
ユーザー |
![]() |
提出日時 | 2019-06-28 23:03:35 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 354 ms / 3,000 ms |
コード長 | 1,038 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 34,560 KB |
最終ジャッジ日時 | 2024-07-02 05:07:11 |
合計ジャッジ時間 | 2,710 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#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 << 18][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] = max(graph[a][b], 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] && !(s & (1 << i))) { ret = max(ret, dfs(i, s | (1 << i)) + graph[pos][i]); } } return dp[s][pos] = ret; }