結果

問題 No.1473 おでぶなおばけさん
ユーザー aqua_tenhouaqua_tenhou
提出日時 2021-04-09 22:04:23
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 810 bytes
コンパイル時間 455 ms
コンパイル使用メモリ 86,960 KB
実行使用メモリ 147,040 KB
最終ジャッジ日時 2023-09-07 11:23:06
合計ジャッジ時間 23,820 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
71,280 KB
testcase_01 AC 95 ms
71,436 KB
testcase_02 AC 1,384 ms
133,492 KB
testcase_03 AC 851 ms
124,452 KB
testcase_04 AC 1,273 ms
105,176 KB
testcase_05 AC 507 ms
86,356 KB
testcase_06 AC 1,608 ms
121,732 KB
testcase_07 AC 1,344 ms
128,828 KB
testcase_08 TLE -
testcase_09 AC 1,108 ms
133,124 KB
testcase_10 AC 486 ms
107,660 KB
testcase_11 AC 576 ms
107,168 KB
testcase_12 AC 455 ms
107,568 KB
testcase_13 AC 341 ms
97,160 KB
testcase_14 AC 311 ms
91,480 KB
testcase_15 AC 502 ms
104,336 KB
testcase_16 AC 428 ms
105,876 KB
testcase_17 AC 154 ms
79,904 KB
testcase_18 AC 191 ms
81,476 KB
testcase_19 AC 560 ms
101,604 KB
testcase_20 AC 669 ms
124,660 KB
testcase_21 AC 939 ms
117,376 KB
testcase_22 AC 542 ms
143,076 KB
testcase_23 AC 475 ms
139,120 KB
testcase_24 AC 465 ms
132,500 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 719 ms
93,400 KB
testcase_28 AC 1,661 ms
134,464 KB
testcase_29 AC 1,037 ms
117,744 KB
testcase_30 AC 1,514 ms
120,348 KB
testcase_31 AC 1,114 ms
147,040 KB
testcase_32 AC 991 ms
131,192 KB
testcase_33 AC 776 ms
122,052 KB
testcase_34 AC 603 ms
102,644 KB
testcase_35 AC 469 ms
102,716 KB
testcase_36 AC 909 ms
107,876 KB
testcase_37 AC 1,512 ms
119,440 KB
testcase_38 AC 295 ms
84,036 KB
testcase_39 AC 449 ms
106,568 KB
testcase_40 AC 425 ms
106,416 KB
testcase_41 AC 510 ms
117,808 KB
testcase_42 AC 489 ms
117,684 KB
testcase_43 AC 467 ms
119,988 KB
testcase_44 AC 466 ms
119,872 KB
testcase_45 AC 477 ms
119,988 KB
testcase_46 AC 719 ms
117,460 KB
testcase_47 AC 844 ms
120,472 KB
testcase_48 AC 624 ms
124,772 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def is_ok(arg):
    w = BWS(arg)
    return w != float("Inf")


def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

def BWS(w):
    q = deque([])
    reach = [float("Inf")]*(n+1)

    q.append(1)
    reach[1] = 0
    while q:
        x = q.popleft()
        for y,z in V[x]:
            if reach[y] == float("Inf") and w <= z:
                q.append(y)
                reach[y] = reach[x] + 1
    return reach[-1]


n,m = map(int,input().split())
z = [list(map(int,input().split())) for i in range(m)]
V = [[] for i in range(n+1)]
for s,t,d in z:
    V[s].append([t,d])
    V[t].append([s,d])

ans = meguru_bisect(10**9 + 1, 0)
print(ans, BWS(ans))
0