[백준] 11404번 : 플로이드 (python 파이썬)

👉 11404번 : 플로이드

---

✍ 내 코드

---

# 골드 4레벨        플로이드
# 플로이드 와샬 알고리즘
from sys import stdin, maxsize

read = stdin.readline

n = int(read())
m = int(read())

graph = [[maxsize] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    graph[i][i] = 0

for _ in range(m):
    s, e, w = map(int, read().split())
    if graph[s][e] > w:
        graph[s][e] = w


def floyd():
    for cross in range(1, n + 1):
        for s in range(1, n + 1):
            if cross == s:
                continue
            for e in range(1, n + 1):
                if cross == e or s == e:
                    continue

                if graph[s][e] > graph[s][cross] + graph[cross][e]:
                    graph[s][e] = graph[s][cross] + graph[cross][e]


floyd()
for s in range(1, n + 1):
    for e in range(1, n + 1):
        if graph[s][e] == maxsize:
            print(0, end=" ")
        else:
            print(graph[s][e], end=" ")
    print()

---

✍ 팁

• 모든 정점에서 모든 정점의 최단 경로를 구해야하는 문제는 플로이드 와샬 알고리즘을 이용해야한다.
• 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 의거한다.