結果
問題 |
No.2805 Go to School
|
ユーザー |
![]() |
提出日時 | 2024-09-28 00:00:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,941 ms / 2,000 ms |
コード長 | 906 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 182,720 KB |
最終ジャッジ日時 | 2025-04-09 15:43:34 |
合計ジャッジ時間 | 27,411 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
from heapq import heappush,heappop n,m,l,s,e=map(int,input().split()) graph=[[] for _ in range(2*n)] for _ in range(m): a,b,c=map(int,input().split()) a,b=a-1,b-1 graph[2*a].append((c,2*b)) graph[2*b].append((c,2*a)) graph[2*a+1].append((c,2*b+1)) graph[2*b+1].append((c,2*a+1)) T=[False]*2*n for t in map(int,input().split()): t-=1 graph[2*t].append((1,2*t+1)) graph[2*t+1].append((0,2*t)) T[2*t+1]=True dist=[float('INF')]*2*n dist[0]=0 que=[(0,0,False)]#(dist,vertex,トイレに既に行ったか) while que: d,v,ok=heappop(que) if d>dist[v]:continue for nc,nv in graph[v]: nd=d+nc if nv%2==1: if T[nv] and not ok and nd>s+e:continue elif T[nv] and not ok:nd=max(nd-1,s)+1 if dist[nv]>nd: dist[nv]=nd heappush(que,(nd,nv,ok or T[nv])) print(dist[-1] if dist[-1]!=float('INF') else -1)