結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-22 00:15:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 839 ms / 2,000 ms |
コード長 | 837 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 124,028 KB |
最終ジャッジ日時 | 2025-06-20 01:57:48 |
合計ジャッジ時間 | 8,053 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
import sys input = sys.stdin.readline from heapq import heappop,heappush N,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]=0 while Q: time,now=heappop(Q) if DIS[now]!=time: continue for to,cost in EDGE[now]: if DIS[to]>DIS[now]+cost: DIS[to]=DIS[now]+cost heappush(Q,(DIS[to],to)) return DIS D1=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)