結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
|
提出日時 | 2024-11-04 09:00:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 623 bytes |
コンパイル時間 | 530 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 112,848 KB |
最終ジャッジ日時 | 2024-11-04 09:00:33 |
合計ジャッジ時間 | 16,863 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 42 |
ソースコード
from collections import deque N,M = map(int,input().split()) G = {i:[] for i in range(1,N+1)} for _ in range(M): s,t,d = map(int,input().split()) G[s].append((t,d)) G[t].append((s,d)) high = 10**9+10 low = 0 ans = -1 while high-low>1: mid = (high+low)//2 dist = [-1]*(N+1) dist[1] = 0 que = deque([1]) while que: x = que.popleft() for y,d in G[x]: if dist[y]==-1 and mid<=d: dist[y] = dist[x]+1 que.append(y) if dist[N]>=0: ans = dist[N] low = mid else: high = mid print(low,ans)