結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー Kohei
提出日時 2026-11-09 21:31:33
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 112 ms / 5,000 ms
+ 67µs
コード長 974 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 103 ms
コンパイル使用メモリ 64,512 KB
実行使用メモリ 63,360 KB
最終ジャッジ日時 2026-11-09 21:31:38
合計ジャッジ時間 3,976 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 1e18
from heapq import heappush, heappop
def main():
    N, M, S, T = map(int, input().split())
    G = [list() for _ in range(N)]
    for i in range(M):
        u, v, w = map(int, input().split())
        G[u].append((v, w))
        G[v].append((u, w))

    # T --> S に最短距離
    kakutei = [False] * (N)
    prev = [N]*N
    dist = [INF] * (N)
    dist[T] = 0
    prev[T] = -1
    que = []
    heappush(que, (0, -1, T))
    while que:
        curr_dist, pre, pos = heappop(que)
        if kakutei[pos]:
            continue
        kakutei[pos] = True
        prev[pos] = pre
        for nex, kyori in G[pos]:
            if kakutei[nex]:
                continue
            if dist[nex] >= curr_dist + kyori:
                dist[nex] = curr_dist + kyori
                heappush(que, (dist[nex], pos, nex))
    ans = []
    pos = S
    while pos != -1:
        ans.append(pos)
        pos = prev[pos]
    print(*ans)

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