結果
問題 |
No.848 なかよし旅行
|
ユーザー |
![]() |
提出日時 | 2025-04-30 09:31:44 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 980 bytes |
コンパイル時間 | 687 ms |
コンパイル使用メモリ | 82,216 KB |
実行使用メモリ | 112,696 KB |
最終ジャッジ日時 | 2025-04-30 09:31:52 |
合計ジャッジ時間 | 7,523 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 WA * 19 |
ソースコード
from heapq import * N,M,P,Q,T = map(int,input().split()) UV = [list(map(int,input().split())) for _ in range(M)] E = [[] for _ in range(N)] P -= 1 Q -= 1 for u, v, c in UV: u -= 1 v -= 1 E[u].append((v,c)) E[v].append((u,c)) INF = 10 ** 13 # N * maxコストくらいで設定 #普通のダイクストラ def dijkstra(x): D = [INF] * N D[x] = 0 q = [(0, x)] while q: d, u = heappop(q) #下のifでTLE解消することがある if d > D[u]: continue for i in E[u]: a,b = i if D[a] > D[u] + b: D[a] = D[u] + b heappush(q, (D[a], a)) return D D0 = dijkstra(0) DP = dijkstra(P) DQ = dijkstra(Q) d0p = D0[P] d0q = D0[Q] dpq = DP[Q] if d0p + d0q +dpq <= T: print(T) exit() ans = -1 for i in range(N): d0i = D0[i] dip = DP[i] diq = DQ[i] mdi = max(dip, diq) if (d0i + mdi) * 2 <= T: ans = max(ans,T - mdi * 2) print(ans)