結果

問題 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
コンパイル時間 231 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 57,372 KB
最終ジャッジ日時 2024-04-19 11:22:18
合計ジャッジ時間 11,028 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
10,880 KB
testcase_01 AC 27 ms
10,752 KB
testcase_02 AC 1,166 ms
53,700 KB
testcase_03 AC 1,609 ms
46,820 KB
testcase_04 AC 455 ms
33,852 KB
testcase_05 AC 268 ms
18,964 KB
testcase_06 AC 1,857 ms
48,712 KB
testcase_07 AC 724 ms
57,372 KB
testcase_08 AC 793 ms
56,920 KB
testcase_09 AC 759 ms
56,576 KB
testcase_10 AC 657 ms
32,128 KB
testcase_11 AC 811 ms
30,592 KB
testcase_12 AC 856 ms
32,640 KB
testcase_13 AC 369 ms
22,784 KB
testcase_14 AC 243 ms
19,584 KB
testcase_15 AC 490 ms
27,648 KB
testcase_16 AC 721 ms
31,104 KB
testcase_17 AC 62 ms
12,160 KB
testcase_18 AC 96 ms
13,056 KB
testcase_19 AC 924 ms
32,316 KB
testcase_20 AC 1,467 ms
42,688 KB
testcase_21 AC 1,029 ms
41,508 KB
testcase_22 AC 608 ms
42,828 KB
testcase_23 AC 499 ms
39,624 KB
testcase_24 AC 501 ms
38,200 KB
testcase_25 AC 609 ms
44,836 KB
testcase_26 AC 639 ms
46,052 KB
testcase_27 AC 232 ms
23,168 KB
testcase_28 AC 836 ms
54,324 KB
testcase_29 AC 1,245 ms
40,112 KB
testcase_30 AC 1,625 ms
45,952 KB
testcase_31 AC 856 ms
53,324 KB
testcase_32 TLE -
testcase_33 AC 1,159 ms
42,484 KB
testcase_34 AC 432 ms
27,372 KB
testcase_35 AC 621 ms
29,352 KB
testcase_36 AC 474 ms
35,196 KB
testcase_37 AC 478 ms
39,844 KB
testcase_38 AC 107 ms
16,384 KB
testcase_39 AC 660 ms
31,360 KB
testcase_40 AC 666 ms
31,232 KB
testcase_41 AC 399 ms
27,964 KB
testcase_42 AC 391 ms
28,160 KB
testcase_43 AC 570 ms
46,444 KB
testcase_44 AC 574 ms
46,312 KB
testcase_45 AC 568 ms
46,180 KB
testcase_46 AC 475 ms
41,444 KB
testcase_47 AC 577 ms
47,172 KB
testcase_48 AC 528 ms
44,912 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