[白準14284]幹線接続2

7335 ワード
パイ アルゴリズム#アルゴリズム# 金貨 白駿 コーディングテスト テキストリンク

1.問題の説明


接続幹線2

2.問題分析


典型的なマルチアウトレット

3.私の回答

import sys
import heapq

INF = sys.maxsize
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])

s, t = map(int, sys.stdin.readline().rstrip().split())

def Dijkstra():
    distances = [INF for _ in range(n+1)]
    distances[s] = 0
    pq = []
    heapq.heappush(pq, [0, s])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)

        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[next_node] > next_cost + cur_cost:
                distances[next_node] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_node])

    return distances[t]

print(Dijkstra())
WEBPilot紹介
jacksonシーケンス化所与のClassマッピングと抽象クラスによるマッピング