[BOJ 11404] 플로이드 (Python)

💡Problem Solving/BOJ

[BOJ 11404] 플로이드 (Python)

gom20 2022. 11. 22. 14:57

문제

https://www.acmicpc.net/problem/11404

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

풀이

floyd 알고리즘

소스코드

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

arr = [[1e9]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            arr[i][j] = 0

for _ in range(m):
    i, j, cost = map(int, input().split())
    arr[i][j] = min(arr[i][j], cost)

for k in range(1 ,n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

for i in range(1, n+1):

    for j in range(1, n+1):
        if arr[i][j] == 1e9:
            arr[i][j] = 0
        print(arr[i][j], end= ' ')
    print()