結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
![]() |
提出日時 | 2021-04-09 21:44:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 559 ms / 2,000 ms |
コード長 | 1,286 bytes |
コンパイル時間 | 1,293 ms |
コンパイル使用メモリ | 82,080 KB |
実行使用メモリ | 110,776 KB |
最終ジャッジ日時 | 2024-06-25 04:51:34 |
合計ジャッジ時間 | 18,216 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
import heapq def dijkstra(G, start=0): n = len(G) dist = [-1] * n Q = [] dist[start] = 0 heapq.heappush(Q, (0, start)) while Q: p = heapq.heappop(Q) v = p[1] d = dist[v] if d < p[0]: continue for nv, nc in G[v]: if dist[nv] == -1 or d + nc < dist[nv]: dist[nv] = d + nc heapq.heappush(Q, (d + nc, nv)) return dist def dijkstra_max(G, start=0): inf = 10**10 n = len(G) dist = [-1] * n Q = [] dist[start] = inf heapq.heappush(Q, (-inf, start)) while Q: p = heapq.heappop(Q) v = p[1] d = dist[v] if d < p[0]: continue for nv, nc in G[v]: if dist[nv] == -1 or min(d, nc) > dist[nv]: dist[nv] = min(d, nc) heapq.heappush(Q, (-min(d, nc), nv)) return dist n, m = map(int, input().split()) G = [[] for _ in range(n)] for _ in range(m): s, t, d = map(int, input().split()) s -= 1 t -= 1 G[s].append((t, d)) G[t].append((s, d)) L = dijkstra_max(G) w = L[n-1] T = [[] for _ in range(n)] for v, g in enumerate(G): for nv, d in g: if w <= d: T[v].append((nv, 1)) ans = dijkstra(T)[n-1] print(w, ans)