結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー norioc
提出日時 2025-06-10 22:26:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,335 ms / 2,000 ms
コード長 1,034 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 152,756 KB
最終ジャッジ日時 2025-06-10 22:26:38
合計ジャッジ時間 20,581 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque


def bsearch(low: int, high: int, fun, is_complement=False) -> int:
    def pred(x: int) -> bool:
        return not fun(x) if is_complement else fun(x)

    lo = low
    hi = high
    res = low
    while lo <= hi:
        m = (lo + hi) // 2
        if pred(m):
            res = max(res, m)
            lo = m + 1
        else:
            hi = m - 1

    return res + 1 if is_complement else res


def calc(weight: int) -> int:
    q = deque([(0, 0)])
    used = {0}
    while q:
        v, step = q.popleft()
        if v == N-1: return step

        for to, d in adj[v]:
            if weight > d: continue
            if to in used: continue
            used.add(to)
            q.append((to, step+1))

    return -1


N, M = map(int, input().split())
adj = defaultdict(list)
for _ in range(M):
    s, t, d = map(int, input().split())
    s -= 1
    t -= 1
    adj[s].append((t, d))
    adj[t].append((s, d))

w = bsearch(1, 10**9, lambda x: calc(x) > 0)
step = calc(w)
print(w, step)
0