結果
問題 |
No.2805 Go to School
|
ユーザー |
![]() |
提出日時 | 2024-07-12 21:31:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 877 ms / 2,000 ms |
コード長 | 890 bytes |
コンパイル時間 | 584 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 124,752 KB |
最終ジャッジ日時 | 2025-04-09 15:37:13 |
合計ジャッジ時間 | 15,124 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
from heapq import heappush, heappop N, M, L, S, E = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): a, b, t = map(int, input().split()) G[a-1].append((b-1, t)) G[b-1].append((a-1, t)) T = list(map(int, input().split())) INF = 10**18 def dijkstra(start): dist = [INF]*N dist[start] = 0 visited = [False]*N que = [(0, start)] while que: d, now = heappop(que) if visited[now]: continue visited[now] = True for next, weight in G[now]: if dist[now]+weight < dist[next]: dist[next] = dist[now]+weight heappush(que, (dist[next], next)) return dist distS = dijkstra(0) distG = dijkstra(N-1) ans = INF for i in range(L): if distS[T[i]-1] <= S+E-1: ans = min(ans, max(distS[T[i]-1], S)+1+distG[T[i]-1]) print(ans if ans != INF else -1)