5972. 택배 배송

문제의 내용이 궁금하시다면, 아래의 링크를 눌러보세요!
문제 보러 가기

접근 과정

농부 현서는, 농부 찬홍이에게 택배를 배달해주는 과정에서 최소한의 소들을 만나면서 이동하고 싶다.
상세히 말하자면, 그래프상의 한 정점에서 다른 정점으로 이동하는 과정에서, 간선으로부터 오는 비용을 최소화하는 최단 경로를 구하고 싶다는 내용으로 정리할 수 있다!

정점의 개수 N과 간선의 개수 M은 각각 1부터 5만까지이다. 그리고, 각 간선의 가중치(비용)은 0부터 1000까지이다. 이 부분을 통해, 음의 가중치를 가지는 간선이 없다는 것을 파악할 수 있다!!

이를 통해 그래프 상에서의 최단 경로를 구해야겠다고 생각했고, 그 중에서도 다익스트라 알고리즘을 사용해 문제를 풀기로 하였다.

정리하면...

• 그래프 상의 정점에서 다른 정점으로 이동하는 최단 경로를 구해야 한다.
• 간선들은 음의 가중치를 가지지 않기 때문에, 다익스트라 알고리즘을 이용할 수 있다.
• 출발 노드를 설정한 후, 거리 테이블을 초기화한다.
• 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하고, 다른 노드를 방문하는 비용을 계산하며, 최단 거리 테이블을 갱신해간다!

풀이

import heapq
import sys

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]:
            if dist + i[1] < distance[i[0]]:
                distance[i[0]] = dist + i[1]
                heapq.heappush(q, (dist + i[1], i[0]))

input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
distance = [0xffffff] * (N + 1)

for i in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

dijkstra(1)
print(distance[N])