結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:08:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,113 ms / 2,000 ms |
コード長 | 1,221 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 156,244 KB |
最終ジャッジ日時 | 2025-06-20 01:55:32 |
合計ジャッジ時間 | 9,802 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
N,M=map(int,input().split()) G1=[[] for _ in range(N+1)] G2=[[] for _ in range(N+1)] for _ in range(M): u,v,t=map(int,input().split()) G1[u].append([v,t]) G2[v].append([u,t]) import sys import heapq def dijkstra(graph, start): # 初期化 n = len(graph) visited = [False] * n distance = [10**19] * n distance[start] = 0 pq = [(0, start)] # ダイクストラ法 while pq: # 未処理の中で最小の距離を持つ頂点を取り出す dist, u = heapq.heappop(pq) if visited[u]: continue # 訪問済みにする visited[u] = True # uから到達可能な頂点の距離を更新する for v, weight in graph[u]: if not visited[v]: new_distance = distance[u] + weight if new_distance < distance[v]: distance[v] = new_distance heapq.heappush(pq, (new_distance, v)) return distance d1=dijkstra(G1,N-1)#N-1からの最短 d2=dijkstra(G1,N) d3=dijkstra(G2,N-1)#N-1への最短 d4=dijkstra(G2,N) for i in range(1,N-1): ans=min(d3[i]+d1[N]+d2[i],d4[i]+d2[N-1]+d1[i]) if(ans>=10**19): ans=-1 print(ans)