🔥

문제

민기는 택배 기사로, 알고 농장에서 근무하고 있다. 알고 농장에는 N(1≤N≤50000)개의 헛간이 있고, 헛간은 1~N까지 번호가 매겨져있다.
민기는 1번 헛간에서 N번 헛간으로 배달을 가려고 한다.


헛간에서 다른 헛간으로 이동하는 길에는 소들이 있다. 이 소들은 길을 막고 있는데, 비키게 하기 위해선 만나는 모든 소들에게 맛있는 여물을 줘야 한다.
민기는 소들을 싫어하기 때문에 최소한의 소들을 만나면서 배달을 하고 싶어한다.


민기에게는 농장 지도가 있다. 지도에는 총 M (1≤M≤50,000)개의 양방향 길이 그려져 있다. i 번째 길은 Ai와 Bi농장을 연결하고 (1≤Ai≤N; 1≤Bi≤N; Ai≠bi)Ci(0≤Ci≤1000)마리의 소가 있다.
두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있다.


다음 지도은 지도의 예시이다.



민기가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 이다. 만나는 소들의 총 합이 1 + 0 + 3 + 1 = 5 로 최소이기 때문이다.
각 길의 정보가 주어질 때, 민기가 만나야 할 소들은 최소 몇 마리인지 구하는 프로그램을 작성하여라

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어진다. 둘째 줄부터 M+1번째 줄까지 세 개의 정수 Ai, Bi, Ci가 주어진다.

출력

첫째 줄에 민기가 최소 몇 마리의 소를 만나야 하는지 출력하라.

예제 1 입력

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

예제 1 출력

5

Source

from queue import PriorityQueue

pq = PriorityQueue()

n, m = map(int, input().split())
edge = [[] for _ in range(n + 1)]
dist = [0 for _ in range(n + 1)]

for i in range(m):
	a, b, c = map(int, input().split())
	edge[a].append((b, c))
	edge[b].append((a, c))

pq.put((1, 1))
while(not pq.empty()):
	tmp = pq.get()
	d = tmp[0]
	v = tmp[1]

	# 이미 방문한 곳이면
	if(dist[v] > 0):
		continue
	dist[v] = d

	# v 정점에서 출발하는 모든 간선(edge)
	for e in edge[v]:
		_d = e[1] # 간선의 가중치
		u = e[0] # 인접한 정점
		pq.put((d + _d, u))

# 정점 번호 및 초기 거릿값을 1로 설정하였기 때문에 -1을 해중
print(dist[n] - 1)

참고