BOJ 1916 최소 비용 구하기

https://www.acmicpc.net/problem/1916
시간 0.5초, 메모리 128MB
input :

• 도시의 개수 N(1 ≤ N ≤ 1,000)
• 버스의 개수 M(1 ≤ M ≤ 100,000)
• 출발 도시의 번호, 도착지의 도시 번호, 버스 비용 (0 <= 버스 비용 <= 100,000)
• 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호

output :

• 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력

조건 :

• 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

---

출발도시에서 도착 지점에 해당하는 거리의 최소를 구해야 한다.
ans 배열을 만들어 출발 도시에서 부터의 모든 정점에 대한 거리를 구한 후 출력하자.

이때에 ans 배열안에 존재하는 도시의 값이 현재 온 거리보다 길다면 업데이트가 필요하다.

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]

for i in range(m):
    a, b, cost = map(int, sys.stdin.readline().split())
    graph[a].append((b, cost))

start, end = map(int, sys.stdin.readline().split())
ans = [float('INF')] * (n + 1)
ans[start] = 0
q = deque([start])

while q:
    now = q.popleft()

    for node, cost in graph[now]:
        if ans[node] > ans[now] + cost:
            ans[node] = ans[now] + cost
            q.append(node)

print(ans[end])

언제나 도착이 가능하다 했으니 INF에 대한 예외처리는 필요가 없다.