結果
問題 | No.845 最長の切符 |
ユーザー |
![]() |
提出日時 | 2019-06-28 21:58:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,517 bytes |
コンパイル時間 | 768 ms |
コンパイル使用メモリ | 78,196 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-02 04:42:21 |
合計ジャッジ時間 | 1,811 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 WA * 23 |
ソースコード
#include <iostream>#include <queue>#include <utility>#include <vector>using namespace std;using int64 = long long;using pll = pair<int64, int64>;struct edge { int64 cost, to; };const int64 INF = 1ll << 60ll;const int64 MINF = -1 * (1ll << 60ll);int64 n, m;vector<struct edge> graph[32];priority_queue<pll> p_que;int64 a, b, c;int64 ans;int64 max_cost[32];int main(){scanf("%lld %lld", &n, &m);for (int64 i = 0; i < m; i++) {scanf("%lld %lld %lld", &a, &b, &c);c = -c;graph[a].emplace_back((struct edge){.cost = c, .to = b});graph[b].emplace_back((struct edge){.cost = c, .to = a});}for (int64 i = 1; i <= n; i++) {for (int64 j = 1; j <= n; j++) max_cost[j] = MINF;max_cost[i] = INF;p_que.push(pll(0, i));while (!p_que.empty()) {pll state = p_que.top();p_que.pop();int64 cost = state.first;int64 pos = state.second;for (int64 j = 0; j < graph[pos].size(); j++) {int64 to = graph[pos][j].to;int64 nc = cost + graph[pos][j].cost;if (max_cost[to] < nc) {max_cost[to] = nc;p_que.push(pll(nc, to));}}}for (int i = 1; i <= n; i++) {if (max_cost[i] != MINF) {ans = max(ans, -max_cost[i]);}}}printf("%lld\n", ans);return 0;}