[白俊]1753番:最短パス解答

7263 ワード
beakjoon グラフ＃グラフ＃ ダエストラ 金貨 白駿 テキストリンク
質問リンク
https://www.acmicpc.net/problem/1753
解き方
  • の既存のマルチアウトレット問題では、K番頂点から各ノード間の距離を出力する問題がある.
  • では、対応するノードに接続されていない場合、距離リストはINF(1 e 9)で格納され、距離がINFに等しい場合は文字列「INF」で置き換えられて出力されるからである.
    • 完全なコード
    from sys import stdin
import heapq

INF = int(1e9)
def dijkstra(i):
    queue = []
    heapq.heappush(queue, (0, i))
    distance = [INF] * (V+1)
    distance[i] = 0

    while queue:
        dist, index = heapq.heappop(queue)

        if distance[index] < dist:
            continue

        for node_index, node_dist in graph[index]:
            cost = dist + node_dist

            if distance[node_index] > cost:
                distance[node_index] = cost

                heapq.heappush(queue, (cost, node_index))

    return distance

V, E = map(int, stdin.readline().split())
graph = {}
for i in range(1, V+1):
    graph[i] = []

K = int(input())
for _ in range(E):
    u, v, w = map(int, stdin.readline().split())
    graph[u].append([v, w])

ans = dijkstra(K)
for i in ans[1:]:
    if i == INF:
        print("INF")
    else:
        print(i)
    Spring BootからDB接続
    if~else文法とif~else文法の違い