結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
👑 |
提出日時 | 2023-12-10 18:45:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 882 ms / 2,000 ms |
コード長 | 1,013 bytes |
コンパイル時間 | 342 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 120,508 KB |
最終ジャッジ日時 | 2024-09-27 04:09:03 |
合計ジャッジ時間 | 7,261 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
import heapqdef dijkstra(edges, s=0, inf=1 << 60):"""edges[from] = [(to1, cost1), (to2, cost2), ...)]"""n = len(edges)dist = [inf] * ndist[s] = 0hq = [s]while hq:tmp = heapq.heappop(hq)d = tmp // npos = tmp - n * dif dist[pos] < d:continuefor npos, c in edges[pos]:if dist[npos] > dist[pos] + c:dist[npos] = dist[pos] + cheapq.heappush(hq, npos + n * dist[npos])return distn, m = map(int, input().split())E = [[] for _ in range(n)]revE = [[] for _ in range(n)]for _ in range(m):u, v, w = map(int, input().split())u -= 1v -= 1E[u].append((v, w))revE[v].append((u, w))d1 = dijkstra(E, n - 1)dr1 = dijkstra(revE, n - 1)d2 = dijkstra(E, n - 2)dr2 = dijkstra(revE, n - 2)for i in range(n - 2):mi = dr1[i] + d1[n - 2] + d2[i]mi = min(mi, dr2[i] + d2[n - 1] + d1[i])if mi >= 1 << 60:mi = -1print(mi)