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

문제

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

 

소스코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[1e11 for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(n):
    graph[i + 1][i + 1] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if graph[i][k] < 1e11 and graph[k][j] < 1e11:
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in range(n):
    for j in range(n):
        if graph[i + 1][j + 1] >= 1e11:
            print(0, end = " ")
        else:
            print(graph[i+1][j+1] , end = " ")
    if i != n - 1:
        print()

 

플로이드 워셜 알고리즘 문제입니다. 

O(V^3)의 속도로 여러 정점에서 여러 정점으로 가는 가장 적은 비용을 알 수 있습니다.

플로이드워셜은 특성상 그래프 표현 방식 중 인접 행렬을 많이 사용합니다.

플로이드 워셜의 삼중 반복문