[백준] 최소비용 구하기

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

1916번: 최소비용 구하기

 

출발 도시와 도착 도시가 같은 버스가 있을 수 있다는 생각을 처음에 못 했다. 그래서 코드를 추가했고 비용이 0인 버스가 있어서 fee = {} 비어있을 때랑 값이 있을 때 나눠서 다익스트라 알고리즘으로 풀었다.

 

import sys
from collections import defaultdict, deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
bus = [list(map(int, sys.stdin.readline().split())) for i in range(M)]
start, end = map(int, sys.stdin.readline().split())
dic = defaultdict(list)
fee = {}
queue = deque()

for x, y, d in bus:
    dic[x].append((y, d))

fee[start] = 0
    
for y, d in dic[start]:
    if y not in fee:
        fee[y] = d
        
        if y != end:
            queue.append(y)
    else:
        if fee[y] > d:
            fee[y] = d
    
while queue:
    x = queue.popleft()
    
    for y, d in dic[x]:
        if y not in fee:
            fee[y] = fee[x] + d
            
            if y != end:
                queue.append(y)
        else:
            if fee[y] > fee[x] + d:
                fee[y] = fee[x] + d
                
                if y != end:
                    queue.append(y)
                
print(fee[end])