結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
![]() |
提出日時 | 2023-04-29 17:50:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,412 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 556,628 KB |
最終ジャッジ日時 | 2024-11-18 12:14:57 |
合計ジャッジ時間 | 51,358 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 TLE * 7 MLE * 2 |
ソースコード
# 体重何キロまで行ける、は単調なので二分探索可能 N, M = map(int, input().split()) edge_list = [] for i in range(M): s, t, d = map(int, input().split()) edge_list.append((s, t, d)) from heapq import heappush, heappop INF = 10 ** 18 def dijkstra(s, n, connect): #(始点, ノード数) distance = [INF] * n que = [(0, s)] #(distance, node) distance[s] = 0 confirmed = [False] * n # ノードが確定済みかどうか while que: w,v = heappop(que) if distance[v]<w: continue confirmed[v] = True for to, cost in connect[v]: # ノード v に隣接しているノードに対して if confirmed[to] == False and distance[v] + cost < distance[to]: distance[to] = distance[v] + cost heappush(que, (distance[to], to)) return distance def check(W): #W = 3 edges = [[] for i in range(N+1)] for s, t, d in edge_list: if d >= W: edges[s].append((t, 1)) edges[t].append((s, 1)) distance = dijkstra(1, N+1, edges) #print(distance) if distance[N] == INF: return 0, distance[N] else: return 1, distance[N] OK = 0 NG = 10**9+1 while NG-OK>1: mid = (NG+OK)//2 if check(mid)[0] == 1: OK = mid else: NG = mid ans_W = OK ans_distance = check(ans_W)[1] print(ans_W, ans_distance)