플로이드

 

 

 

유형 파악 및 구현

이 문제는 플로이드-워셜 알고리즘으로 간단히 구현 가능하다.

다만, 이 문제를 풀면서 정확히 정리해야함을 느꼈다.

쉬운문제인만큼 꼼꼼히 봐야한다.

 

Problems

- 간선별로 양방향 노드가 연결된게 아닌데 처리해버림 

- 시작노드와 도착노드를 연결하는 노선은 하나가 아닐 수 있다라는 조건을 놓침

- INF인 경우 0처리 안함.

 

코드

INF = int(1e9)
n = int(input())
m = int(input())

graph = [[INF]*(n+1) for _ in range(n+1)]

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

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


for k in range(1, n+1):
    for x in range(1, n+1):
        for y in range(1, n+1):
            graph[x][y] = min(graph[x][k]+graph[k][y], graph[x][y])


for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print(0, end=" ")
            continue
        print(graph[i][j], end=" ")
    print("")