[백준 문제풀이] 얼렁뚱땅 1916 최소비용 구하기 풀이

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

from collections import deque

n = int(input())
m = int(input())
dict_ = {}
visited = [100000001]*(n+1)


for i in range(m) :
    start, end, money = map(int,input().split())
    if start not in dict_ :
        dict_[start] = [[end,money]]
    else :
        dict_[start].append([end,money])

want_start, want_end = map(int,input().split())

q = deque()
q.append([want_start,0])


while q :
    start, money = q.popleft()
    
    if visited[start] != want_start and visited[start] < money :
        continue

    if start not in dict_ :
        continue
    
    for i in range(len(dict_[start])) :
        if money + dict_[start][i][1] < visited[dict_[start][i][0]] :
            q.append([dict_[start][i][0],money + dict_[start][i][1]])
            visited[dict_[start][i][0]] = money + dict_[start][i][1] 

print(visited[want_end])