백준11404번 플로이드

백준11404번 플로이드

2021.06.20 플로이드

Solution

플로이드 알고리즘으로 해결하였습니다.

1. input
   • start, end 로 2차원 배열(input_map) 에 cost 저장
   • 노선이 여러개일 경우 짧은 것으로 갱신
2. floyd 알고리즘으로 모든 최단 경로 찾기
3. 결과가 inf 인 경우, 경로가 없는 것이므로 0으로 수정 (문제 조건)

Source

# 2021.06.20
inf = int(1e9)

def floyd(input_map, V):
    for i in range(V):
        input_map[i][i] = 0

    for k in range(V):
        for i in range(V):
            for j in range(V):
                input_map[i][j] = min(input_map[i][j], input_map[i][k] + input_map[k][j])

    for i in range(V):
        for j in range(V):
            if input_map[i][j] == inf:
                input_map[i][j] = 0

    return input_map

V = int(input())
M = int(input())
input_map = [[inf] * V for _ in range(V)]
for _ in range(M):
    start, end, cost = map(int, input().split())
    input_map[start-1][end-1] = min(cost, input_map[start-1][end-1])

result = floyd(input_map, V)
for i in range(V):
    print(*result[i])