結果

問題 No.1473 おでぶなおばけさん
ユーザー 👑 hitonanodehitonanode
提出日時 2021-04-04 18:36:12
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,165 ms / 2,000 ms
コード長 1,047 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 10,972 KB
実行使用メモリ 47,704 KB
最終ジャッジ日時 2023-08-27 19:36:02
合計ジャッジ時間 25,946 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 20 ms
8,540 KB
testcase_01 AC 19 ms
8,616 KB
testcase_02 AC 1,104 ms
46,464 KB
testcase_03 AC 606 ms
42,252 KB
testcase_04 AC 603 ms
28,660 KB
testcase_05 AC 236 ms
17,388 KB
testcase_06 AC 1,095 ms
44,044 KB
testcase_07 AC 781 ms
47,564 KB
testcase_08 AC 1,165 ms
47,704 KB
testcase_09 AC 766 ms
47,556 KB
testcase_10 AC 660 ms
36,384 KB
testcase_11 AC 730 ms
35,248 KB
testcase_12 AC 634 ms
37,024 KB
testcase_13 AC 336 ms
23,580 KB
testcase_14 AC 228 ms
20,216 KB
testcase_15 AC 549 ms
32,072 KB
testcase_16 AC 477 ms
35,372 KB
testcase_17 AC 38 ms
10,428 KB
testcase_18 AC 53 ms
11,524 KB
testcase_19 AC 549 ms
28,524 KB
testcase_20 AC 563 ms
33,700 KB
testcase_21 AC 933 ms
35,256 KB
testcase_22 AC 340 ms
33,848 KB
testcase_23 AC 288 ms
30,788 KB
testcase_24 AC 289 ms
29,872 KB
testcase_25 AC 352 ms
36,136 KB
testcase_26 AC 361 ms
37,288 KB
testcase_27 AC 143 ms
20,152 KB
testcase_28 AC 427 ms
41,340 KB
testcase_29 AC 406 ms
32,996 KB
testcase_30 AC 475 ms
36,800 KB
testcase_31 AC 743 ms
46,676 KB
testcase_32 AC 1,031 ms
45,212 KB
testcase_33 AC 504 ms
35,468 KB
testcase_34 AC 347 ms
23,680 KB
testcase_35 AC 321 ms
25,704 KB
testcase_36 AC 266 ms
29,644 KB
testcase_37 AC 283 ms
31,356 KB
testcase_38 AC 63 ms
13,212 KB
testcase_39 AC 515 ms
35,668 KB
testcase_40 AC 464 ms
35,828 KB
testcase_41 AC 319 ms
32,624 KB
testcase_42 AC 317 ms
32,800 KB
testcase_43 AC 547 ms
41,788 KB
testcase_44 AC 540 ms
41,732 KB
testcase_45 AC 558 ms
41,832 KB
testcase_46 AC 299 ms
34,504 KB
testcase_47 AC 378 ms
42,848 KB
testcase_48 AC 433 ms
40,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Python 二分探索解 AC になってほしい
from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    to = [[] for _ in range(N)]
    ds = []
    for _ in range(M):
        s, t, d = map(int, input().split())
        s -= 1
        t -= 1
        to[s].append((t, d))
        to[t].append((s, d))
        ds.append(d)
    
    ds = sorted(set(ds))
    ok, ng = 0, len(ds)

    def calc(th: int):
        dist = [1 << 30] * N
        dist[0] = 0
        q = deque([0])
        while q:
            now = q.popleft()
            for nxt, d in to[now]:
                if d >= th and dist[nxt] > dist[now] + 1:
                    dist[nxt] = dist[now] + 1
                    q.append(nxt)
        return dist[-1]

    while ng - ok > 1:
        c = (ok + ng) // 2
        x = calc(ds[c])
        if x < 1 << 30:
            ok = c
        else:
            ng = c
    print(ds[ok], calc(ds[ok]))

if __name__ == '__main__':
    main()
0