[백준][Python] 11404 플로이드

최단거리 문제연습. 모든 정점에서 모든 정점.

주의 할 점은 동일 출발, 동일 도착 간선이 있고 때문에 입력 시 최솟값만을 입력해주어야함.

플로이드 워샬은 간선이 없는 전 구간에 대해 조사하기 때문에 사실 인접리스트의 의미가 좀 없는 것 같다.

인접행렬로 표현하는게 더 효율저일듯 싶다.

import sys
input = sys.stdin.readline

def floid_washal():
    dp_dists = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
    for cur_node in graph:
        for next_node,dist in graph[cur_node]:
            if dp_dists[cur_node][next_node] > dist:
                dp_dists[cur_node][next_node] = dist
                dp_dists[cur_node][cur_node] = 0

    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                dp_dists[i][j] = min(dp_dists[i][j],dp_dists[i][k]+dp_dists[k][j])
    
    for i in range(1,n+1):
        for j in range(1,n+1):
            if dp_dists[i][j] == float('inf'):
                print(0, end=' ')
            else:
                print(dp_dists[i][j], end=' ')
        print()

n = int(input())
m = int(input())
graph = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append([b,c])

floid_washal()