結果

問題 No.1473 おでぶなおばけさん
ユーザー hiragnhiragn
提出日時 2022-12-04 01:13:00
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,298 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 57,116 KB
最終ジャッジ日時 2024-10-11 03:35:55
合計ジャッジ時間 38,045 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
10,752 KB
testcase_01 AC 28 ms
10,752 KB
testcase_02 AC 1,239 ms
53,708 KB
testcase_03 AC 1,620 ms
46,432 KB
testcase_04 AC 487 ms
33,728 KB
testcase_05 AC 280 ms
18,704 KB
testcase_06 AC 1,913 ms
48,456 KB
testcase_07 AC 801 ms
57,116 KB
testcase_08 AC 792 ms
56,860 KB
testcase_09 AC 743 ms
56,428 KB
testcase_10 AC 687 ms
31,872 KB
testcase_11 AC 800 ms
30,592 KB
testcase_12 AC 848 ms
32,512 KB
testcase_13 AC 389 ms
22,784 KB
testcase_14 AC 261 ms
19,328 KB
testcase_15 AC 517 ms
27,392 KB
testcase_16 AC 717 ms
30,848 KB
testcase_17 AC 67 ms
11,776 KB
testcase_18 AC 101 ms
12,672 KB
testcase_19 AC 910 ms
32,192 KB
testcase_20 AC 1,465 ms
42,464 KB
testcase_21 AC 1,018 ms
41,512 KB
testcase_22 AC 603 ms
42,552 KB
testcase_23 AC 504 ms
39,400 KB
testcase_24 AC 506 ms
37,948 KB
testcase_25 AC 619 ms
44,708 KB
testcase_26 AC 659 ms
45,664 KB
testcase_27 AC 258 ms
23,040 KB
testcase_28 AC 892 ms
54,188 KB
testcase_29 AC 1,176 ms
40,112 KB
testcase_30 AC 1,588 ms
45,916 KB
testcase_31 AC 875 ms
53,196 KB
testcase_32 TLE -
testcase_33 AC 1,198 ms
42,388 KB
testcase_34 AC 435 ms
26,988 KB
testcase_35 AC 621 ms
28,964 KB
testcase_36 AC 503 ms
35,324 KB
testcase_37 AC 495 ms
39,840 KB
testcase_38 AC 117 ms
16,108 KB
testcase_39 AC 702 ms
31,104 KB
testcase_40 AC 670 ms
31,104 KB
testcase_41 AC 426 ms
27,960 KB
testcase_42 AC 429 ms
28,288 KB
testcase_43 AC 624 ms
46,184 KB
testcase_44 AC 613 ms
46,440 KB
testcase_45 AC 616 ms
46,180 KB
testcase_46 AC 512 ms
41,572 KB
testcase_47 AC 624 ms
47,172 KB
testcase_48 AC 560 ms
44,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
https://qiita.com/c-yan/items/1ad8c9d5400077f19459#e-1473-%E3%81%8A%E3%81%A7%E3%81%B6%E3%81%AA%E3%81%8A%E3%81%B0%E3%81%91%E3%81%95%E3%82%93

c-yanさんのqiita記事の変数名をいじっただけ。
"""
from collections import defaultdict, deque


def main():
    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))

    q = deque([(0, 10 ** 15)])
    # (都市iに到達可能な体重wのmax)
    # = (その経路のdのmin)
    # dp[i]:(都市iまでの経路のdのmin, 対応するパス長)
    dp = [(-1, -1) for _ in range(n)]
    dp[0] = (10 ** 15, 0)
    while q:
        cur_city, cur_d = q.popleft()
        if dp[cur_city][0] > cur_d:
            continue
        for nxt_city, nxt_d in adj[cur_city]:
            new_d = min(cur_d, nxt_d)
            if dp[nxt_city][0] >= new_d:
                continue
            if dp[nxt_city][0] == new_d:
                dp[nxt_city] = (new_d, min(dp[nxt_city][1], dp[cur_city][1] + 1))
            else:
                dp[nxt_city] = (new_d, dp[cur_city][1] + 1)
            q.append((nxt_city, new_d))
    print(*dp[n - 1])


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