結果
問題 |
No.1473 おでぶなおばけさん
|
ユーザー |
|
提出日時 | 2021-04-09 22:36:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 717 ms / 2,000 ms |
コード長 | 739 bytes |
コンパイル時間 | 357 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 111,872 KB |
最終ジャッジ日時 | 2024-06-25 06:15:22 |
合計ジャッジ時間 | 14,927 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
import sys input = sys.stdin.readline from collections import * def bfs(x): dist = [-1]*n dist[0] = 0 q = deque([0]) while q: v = q.popleft() for nv, d in G[v]: if x<=d and dist[nv]==-1: dist[nv] = dist[v]+1 q.append(nv) return dist[-1] def binary_search(): l, r = 0, 10**10 while l<=r: m = (l+r)//2 if bfs(m)>=0: l = m+1 else: r = m-1 return r n, m = map(int, input().split()) G = [[] for _ in range(n)] for _ in range(m): s, t, d = map(int, input().split()) G[s-1].append((t-1, d)) G[t-1].append((s-1, d)) w = binary_search() print(w, bfs(w))