結果

問題 No.160 最短経路のうち辞書順最小
ユーザー lam6er
提出日時 2025-03-20 21:09:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,012 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 77,588 KB
最終ジャッジ日時 2025-03-20 21:10:03
合計ジャッジ時間 3,429 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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])))
0