結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー wolgnik
提出日時 2021-04-09 21:41:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,339 ms / 2,000 ms
コード長 597 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 109,056 KB
最終ジャッジ日時 2024-06-25 04:45:19
合計ジャッジ時間 21,015 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque as dq
input = sys.stdin.readline
N, M = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))

def check(w):
  Q = dq([1])
  dp = [-1] * (N + 1)
  dp[1] = 0
  while len(Q):
    x = Q.popleft()
    for y, d in e[x]:
      if dp[y] != -1: continue
      if d >= w:
        dp[y] = dp[x] + 1
        Q.append(y)
  return dp[N]

ok = 0
ng = 10 ** 9 + 1
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m) != -1: ok = m
  else: ng = m
print(ok, check(ok))
0