[알고리즘] 플로이드 - 이코테 핵심유형 ( 백준 11404 )

1. 문제

플로이드

2. 접근

1. 하나의 도시에서 다른 도시까지 가는데 모든 노드에서 출발하므로 플로이드워셜 알고리즘 선택 ( 출력되는 예시 값보면 알 수 있음 )

2. 간선의 거리 비용이 주어진것이 아니라서 최소 간선 거리의 비용을 찾아야 한다

3. 각 노드가 갈수있는 모든 노드의 거리를 찾서 for문으로 출력해야한다

 

3. 풀이

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

INF = int(1e9)

graph = [[INF]*(n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 최소 거리 단선만 구하면 되기때문에 크기 비교를 해야한다
for i in range(m):
    a, b, c = map(int, input().split())
    if c < graph[a][b]:
        graph[a][b] = c

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print(0, end=' ')
        else:
            print(graph[a][b], end=' ')

    print()