[백준 1916] 최소비용 구하기

문제

 

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

처음 작성한 코드

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
result = [sys.maxsize] * (N+1)
arr = {i+1:[] for i in range(N)}

for _ in range(M):
    u, v, w = map(int, sys.stdin.readline().split())
    arr[u].append([v,w])

s , e = map(int, sys.stdin.readline().split())

queue = deque()
result[s] = 0
queue.append(s)

while queue:
    u = queue.popleft()
    for v, w in arr[u]:
        if result[v] > result[u] + w:
            result[v] = result[u] + w
            queue.append(v)

print(result[e])

 

깨달은 점

• 단순한 다익스트라를 이용한 문제였다. 한 점에서 다른 점까지 최소거리를 구할 때 다익스트라를 쓰면 되는 것 같다. 손에 익으니까 재밌다 ㅋ ㅋ