結果
問題 | No.1473 おでぶなおばけさん |
ユーザー |
|
提出日時 | 2021-04-09 21:49:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,081 ms / 2,000 ms |
コード長 | 633 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 113,288 KB |
最終ジャッジ日時 | 2024-06-25 05:03:45 |
合計ジャッジ時間 | 18,764 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
from collections import deque n,m = map(int,input().split()) e = [[] for i in range(n)] for i in range(m): s,t,d = map(int,input().split()) s -= 1 t -= 1 e[s].append((t,d)) e[t].append((s,d)) inf = 10**20 def search(M): dis = [inf]*n dis[0] = 0 q = deque([0]) while q: now = q.popleft() for nex,d in e[now]: if d >= M and dis[nex] > dis[now]+1: dis[nex] = dis[now]+1 q.append(nex) return dis[-1] l = 0 r = 10**9+5 while r > l + 1: m = (r+l)//2 if search(m) == inf: r = m else: l = m print(l,search(l))