結果
問題 | No.1473 おでぶなおばけさん |
ユーザー |
|
提出日時 | 2022-08-11 22:27:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 900 ms / 2,000 ms |
コード長 | 1,103 bytes |
コンパイル時間 | 598 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 113,500 KB |
最終ジャッジ日時 | 2024-09-22 05:21:23 |
合計ジャッジ時間 | 15,019 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
from collections import deque import sys input = sys.stdin.readline INF = 1 << 30 n, m = map(int, input().split()) edge = [[] for _ in range(n)] for _ in range(m): s, t, d = map(int, input().split()) s -= 1 t -= 1 edge[s].append((t, d)) edge[t].append((s, d)) left, right = 1, 10**9 + 10 while right - left > 1: mid = (left + right) // 2 Que = deque([0]) C = [INF] * n C[0] = 0 while Que: cp = Que.popleft() if cp == n - 1: break cnt = C[cp] for np, w in edge[cp]: if w < mid: continue if cnt + 1 >= C[np]: continue C[np] = cnt + 1 Que.append(np) if C[n - 1] < INF: left = mid else: right = mid Que = deque([0]) C = [INF] * n C[0] = 0 while Que: cp = Que.popleft() if cp == n - 1: print(left, C[cp]) break cnt = C[cp] for np, w in edge[cp]: if w < left: continue if cnt + 1 >= C[np]: continue C[np] = cnt + 1 Que.append(np)