結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2024-11-29 00:22:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 755 ms / 2,000 ms |
コード長 | 1,106 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,492 KB |
実行使用メモリ | 125,812 KB |
最終ジャッジ日時 | 2024-11-29 00:23:02 |
合計ジャッジ時間 | 6,766 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
from heapq import heappush, heappopN, M = map(int, input().split())G = [[] for _ in range(N)]GR = [[] for _ in range(N)]for _ in range(M):u, v, t = map(int, input().split())G[u-1].append((v-1, t))GR[v-1].append((u-1, t))INF = 10**18def dijkstra(start, G):dist = [INF]*Ndist[start] = 0visited = [False]*Nque = [(0, start)]while que:d, now = heappop(que)if visited[now]:continuevisited[now] = Truefor next, weight in G[now]:if dist[now]+weight < dist[next]:dist[next] = dist[now]+weightheappush(que, (dist[next], next))return distdistN1 = dijkstra(N-2, G)distN = dijkstra(N-1, G)distN1R = dijkstra(N-2, GR)distNR = dijkstra(N-1, GR)for i in range(N-2):ans = INFif distN1R[i] != INF and distN1[N-1] != INF and distN[i] != INF:ans = min(ans, distN1R[i]+distN1[N-1]+distN[i])if distNR[i] != INF and distN[N-2] != INF and distN1[i] != INF:ans = min(ans, distNR[i]+distN[N-2]+distN1[i])print(ans if ans != INF else -1)