結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-22 00:15:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 717 ms / 2,000 ms |
コード長 | 837 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 120,748 KB |
最終ジャッジ日時 | 2024-09-27 11:15:18 |
合計ジャッジ時間 | 5,467 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
import sysinput = sys.stdin.readlinefrom heapq import heappop,heappushN,M=map(int,input().split())E=[[] for i in range(N+1)]E_INV=[[] for i in range(N+1)]for i in range(M):u,v,t=map(int,input().split())E[u].append((v,t))E_INV[v].append((u,t))def distance(x,EDGE):DIS=[1<<60]*(N+1)Q=[(0,x)]DIS[x]=0while Q:time,now=heappop(Q)if DIS[now]!=time:continuefor to,cost in EDGE[now]:if DIS[to]>DIS[now]+cost:DIS[to]=DIS[now]+costheappush(Q,(DIS[to],to))return DISD1=distance(N-1,E)D2=distance(N-1,E_INV)D3=distance(N,E)D4=distance(N,E_INV)for i in range(1,N-1):a=D2[i]+D1[N]+D3[i]b=D4[i]+D3[N-1]+D1[i]ANS=min(a,b)if ANS>1<<60:print(-1)else:print(ANS)