結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-09-30 14:35:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 890 ms / 2,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 335 ms |
コンパイル使用メモリ | 82,636 KB |
実行使用メモリ | 122,608 KB |
最終ジャッジ日時 | 2025-04-09 15:43:54 |
合計ジャッジ時間 | 15,139 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
N,M,L,S,E = map(int, input().split()) edge = [[] for i in range(N)] for i in range(M): a,b,t = map(int, input().split()) a-=1;b-=1 edge[a].append((b,t)) edge[b].append((a,t)) toilet = list(map(int, input().split())) from heapq import heappush, heappop INF = 10**16 def dijkstra(N, edge, s): dist = [INF] * N que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in edge[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist dist1 = dijkstra(N,edge,0) dist2 = dijkstra(N,edge,N-1) #print(dist1) #print(dist2) st,en = S,S+E-1 #print(st,en) ans = 10**16 for i in toilet: i-=1 if dist1[i] < st: now = st+1 elif st <= dist1[i] <= en: now = dist1[i]+1 else: continue if dist2[i] == 10**16: continue now += dist2[i] ans = min(ans,now) print(ans if ans != 10**16 else -1)