[파이썬] 백준 11404 플로이드

플로이드 워셜 알고리즘이고 이를 구현할 줄 몰라서 직접 만들었다. 몇가지 dp 업데이트가 잘 안되서 실패했다.

import sys
from collections import deque
from itertools import combinations
 
def check(k,i,n):
 
    dp = [1000000000]*(n+1) # 0 인덱스는 무시
 
    dp[i] = 0
 
    queue = deque()
 
    check = [ ]
 
    for z in range(0,len(k)):
            start = k[z][0]
            finish = k[z][1]
            price = k[z][2]
 
            if start == i:
 
 
                if price < dp[finish]:
                    dp[finish] = price
 
                check.append(k[z])
                queue.append(k[z])
 
 
 
    print(dp)
 
    while queue:
        start, end, price = queue.popleft()
 
        new_price = dp[start] + price
 
        if new_price<dp[end]:
            dp[end] = price
 
        for i in range(0,len(k)):
            if k[i][0] == end:
 
                if k[i] not in check:
 
                    check.append(k[i])
                    queue.append(k[i])
 
 
 
 
 
    return dp[1:]
 
 
 
n = int(input()) # 도시 개수
m = int(input()) # 버스 수
 
k = [ ]
 
# 출발지, 목적지, 가격
 
for i in range(m):
    a,b,c = list(map(int,sys.stdin.readline().split(" ")))
 
    k.append([a,b,c])
 
k = list(sorted(k))
 
for i in range(1,n+1):
 
    # i 번째 버스에서 각 목적지 까지 가격 최솟값 출력
    check(k,i,n)