https://www.acmicpc.net/problem/1916
시간 2초, 메모리 128MB
input :
- N(1 ≤ N ≤ 1,000)
- M(1 ≤ M ≤ 100,000)
- a b c(a : 출발점, b : 도착점, c : 버스 비용)
output :
- 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
조건 :
- 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다
출발점, 도착점으로 구분이 가기 떄문에 단방향 그래프이다.
모든 이동에 대한 최단거리를 구하기 때문에 이전에 방문했던 노드를 방문하는 경우를 걸러내야 한다.
이를 통해 시간을 많이 단축시킬 수 있다.
최단 거리를 기록하기 위해 현재까지의 이동을 기록해야 한다.
그리고 시작 점에서 부터 다음 노드를 찾아 움직이기 때문에 빠지는 노드 놓치는 엣지들이 없다.
import sys
from heapq import heappop, heappush
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
for i in range(m):
a, b, c = (map(int, sys.stdin.readline().split()))
graph[a].append((b, c))
dist = [float('inf')] * (n + 1)
start, end = map(int, sys.stdin.readline().split())
dist[start] = 0
q = [(0, start)]
while q:
now_cost, now_node = heappop(q)
if dist[now_node] < now_cost:
continue
for next_node, next_cost in graph[now_node]:
cost = now_cost + next_cost
if dist[next_node] > cost:
dist[next_node] = cost
heappush(q, (cost, next_node))
print(dist[end])
