061 플로이드

첫번째 코드

 

플로이드-워셜 방법을 처음 써보았다.

코드는 책을 참고했다.

 

앞서 작성한 다양한 방법의 그래프 문제들의 알고리즘들을 빨리 정리해야할 필요성이 느껴진댜....

복잡하다.. 어렵당;

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
distance = [[sys.maxsize for j in range(n+1)] for i in range(n+1)]

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

for i in range(m):
    s, e, v = map(int, input().split())
    if distance[s][e] > v:
        distance[s][e] = v

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if distance[i][j] > distance[i][k] + distance[k][j]:
                distance[i][j] = distance[i][k] + distance[k][j]

for k in range(1, n+1):
    for j in range(1, n+1):
        if distance[k][j] == sys.maxsize:
            print(0, end = ' ')
        else:
            print(distance[k][j], end = ' ')
    print()

 

통과

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/11404.%E2%80%85%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C

programmers/백준/Gold/11404. 플로이드 at main · ornni/programmers