結果

問題 No.160 最短経路のうち辞書順最小
ユーザー lam6er
提出日時 2025-03-20 21:09:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,012 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,492 KB
実行使用メモリ 77,556 KB
最終ジャッジ日時 2025-03-20 21:10:21
合計ジャッジ時間 2,947 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import heapq
n, m, S, G = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))
    adj[b].append((a, c))
# Dijkstra's algorithm to find shortest distances
INF = float('inf')
dist = [INF] * n
dist[S] = 0
heap = []
heapq.heappush(heap, (0, S))
while heap:
    current_dist, u = heapq.heappop(heap)
    if current_dist > dist[u]:
        continue
    for v, cost in adj[u]:
        if dist[v] > dist[u] + cost:
            dist[v] = dist[u] + cost
            heapq.heappush(heap, (dist[v], v))
# Reconstruct the path from G to S by choosing lex smallest nodes
path = []
current = G
path.append(current)
while current != S:
    min_u = None
    for v, cost in adj[current]:
        if dist[v] + cost == dist[current]:
            if min_u is None or v < min_u:
                min_u = v
    current = min_u
    path.append(current)
# Reverse the path to get the correct order and print
print(' '.join(map(str, path[::-1])))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0