結果
問題 | No.845 最長の切符 |
ユーザー |
![]() |
提出日時 | 2019-06-28 23:03:01 |
言語 | C (gcc 13.3.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,038 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 30,336 KB |
実行使用メモリ | 18,176 KB |
最終ジャッジ日時 | 2024-07-02 05:07:08 |
合計ジャッジ時間 | 2,679 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 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] = 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;}