[백준 14284번] 간선 이어하기 2 - 파이썬(python)

14284번: 간선 이어가기 2

분류

• 그래프 이론
• 데이크스트라

문제

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

입력

첫째 줄에 정점의 개수 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가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오.

풀이

• s에서 t로 가는 최단 거리를 구하는 문제이다.
• 무방향 그래프이므로 양방향 모두 인접리스트에 추가한다.
• 거리를 기록할 배열을 최대값으로 초기화한다.
• 힙큐를 통해 최소 거리를 뽑아내어 값을 갱신한다.

코드

import sys, heapq
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(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())
INF = int(21e8)
dist = [INF]*(n+1)
dist[s] = 0

def dijk(s):
    q = []
    # 시작 값은 0으로 시작
    heapq.heappush(q, (0, s))
    while q:
        cost, node = heapq.heappop(q)
        # 만약 현재노드의 비용이 cost보다 작다면 continue
        if dist[node] < cost: continue
        # 현재 노드의 비용이 더 크다면 최소값을 갱신한다.
        for i in graph[node]:
            if cost + i[1] < dist[i[0]]:
                dist[i[0]] = cost + i[1]
                heapq.heappush(q, (cost + i[1], i[0]))

dijk(s)
print(dist[t])