結果
問題 | No.848 なかよし旅行 |
ユーザー |
![]() |
提出日時 | 2019-07-05 22:11:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 1,085 bytes |
コンパイル時間 | 170 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 102,844 KB |
最終ジャッジ日時 | 2024-11-08 00:50:04 |
合計ジャッジ時間 | 8,004 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import sys from heapq import heappop as hpp, heappush as hp def dijkstra(N, s, Edge): inf = 10**10 dist = [inf] * N Q = [(0, s)] decided = set() for _ in range(N): while True: dn, vn = hpp(Q) if vn not in decided: decided.add(vn) dist[vn] = dn break for vf, df in Edge[vn]: if vf not in decided: hp(Q, (dn + df, vf)) return dist N, M, P, Q, T = map(int, input().split()) P -= 1 Q -= 1 Edge = [[] for _ in range(N)] for _ in range(M): a, b, c = map(int, sys.stdin.readline().split()) a -= 1 b -= 1 Edge[a].append((b, c)) Edge[b].append((a, c)) dist0 = dijkstra(N, 0, Edge) distP = dijkstra(N, P, Edge) distQ = dijkstra(N, Q, Edge) ans = -1 for i in range(N): for j in range(N): t = dist0[i] + dist0[j] + max(distP[i]+distP[j], distQ[i]+distQ[j]) if t > T: continue ans = max(ans, dist0[i] + dist0[j] + T - t) if dist0[P] + distP[Q] + dist0[Q] <= T: ans = T print(ans)