[파이썬] 백준 1753 최단경로

BFS 로 풀었더니 시간 초과가 났고, 다익스트라 알고리즘을 이용하는 문제라고 한다.

import sys
from collections import deque
 
 
 
a,b = list(map(int,sys.stdin.readline().split(" ")))
 
n = int(input())
 
k = [ ]
 
dp = [10000000000]*(a+1)
 
for i in range(0,b):
    k.append(list(map(int,sys.stdin.readline().split(" "))))
 
 
 
queue = deque()
 
# 본인에서 출발인 것들을 queue 에 넣기
 
for i in range(0,len(k)):
    if k[i][0] == n:
        queue.append(k[i])
        dp[k[i][1]] = k[i][2]
 
 
 
check = [ ]
 
 
# bfs 돌리기 - dp 업데이트 하기
 
dp[n] = 0
 
while queue:
 
    start, finish, price = queue.popleft()
 
    dp[finish] = min(dp[finish],dp[start] + price)     
 
    for i in range(0,len(k)):
        if k[i][0] == finish:
            queue.append(k[i])
 
 
 
for i in range(1,len(dp)):
    if dp[i] == 10000000000:
        print('INF')
    else:
        print(dp[i])