[Python] 백준 14284번 간선 이어가기 2

문제

14284번: 간선 이어가기 2

입력

• 첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤5000,1≤m≤100,000)
• 다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다. (1≤a,b≤n,1≤c≤100,a≠b)
• 다음 줄에는 두 정점 s,t가 주어진다. (1≤s,t≤n,s≠t)
• 모든 간선을 연결하면 그래프는 연결 그래프가 됨이 보장된다.

출력

• s와 t가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오,

입력 예제

8 9
1 2 3
1 3 2
1 4 4
2 5 2
3 6 1
4 7 3
5 8 6
6 8 2
7 8 7
1 8

출력 예제

5

풀이

• s와 t가 연결되는 순간 간선 추가를 멈춘 후,  연결되는 순간 가중치의 값이 최소가 되는 값을 구해야 하므로 다익스트라 알고리즘 수행
• 모든 간선들을 입력받은 후, s에서 출발하여 t까지 도착한 최소거리를 출력

코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int,input().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a, c))
s, t = map(int,input().split())

def dijkstra(start):
    q = []
    heapq.heappush(q, (0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(s)
print(distance[t])