結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
![]() |
提出日時 | 2020-12-19 10:40:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 889 ms / 2,000 ms |
コード長 | 1,410 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 82,388 KB |
最終ジャッジ日時 | 2024-09-21 10:09:52 |
合計ジャッジ時間 | 11,855 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
import syssys.setrecursionlimit(10**6)int1 = lambda x: int(x)-1p2D = lambda x: print(*x, sep="\n")def II(): return int(sys.stdin.buffer.readline())def MI(): return map(int, sys.stdin.buffer.readline().split())def MI1(): return map(int1, sys.stdin.buffer.readline().split())def LI(): return list(map(int, sys.stdin.buffer.readline().split()))def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))def LLI(rows_number): return [LI() for _ in range(rows_number)]def BI(): return sys.stdin.buffer.readline().rstrip()def SI(): return sys.stdin.buffer.readline().rstrip().decode()dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]inf = 10**16# md = 998244353md = 10**9+7from heapq import *t=II()n,m=MI()to=[[] for _ in range(n)]uvw=[]for i in range(m):u,v,w=MI()u,v=u-1,v-1to[u].append((v,w,i))if t==0:to[v].append((u,w,i))uvw.append((u,v,w))def solve(s,g):dd=[inf]*nhp=[]heappush(hp,(0,s))dd[s]=0while hp:d,u=heappop(hp)if u==g:return dif d>dd[u]:continuefor v,w,i in to[u]:if fin[i]:continueif dd[v]<=d+w:continuedd[v]=d+wheappush(hp,(d+w,v))return inffin=[False]*mans=inffor i,(u,v,w) in enumerate(uvw):if fin[i]:continuefin[i]=Trueret=solve(v,u)+wif ret<ans:ans=retif ans==inf:print(-1)else:print(ans)