[BOJ/백준] 1719 택배 파이썬

문제 링크 : https://www.acmicpc.net/problem/1719

1719번: 택배

 

문제에 모든 노드가 다 연결되어 있는지 만약 아니라면 그때의 출력은 어찌하는지가 없었다.

그래서 그냥 모든 노드가 연결되어 있다는 가정하에 문제를 풀었다.

 

나는 플로이드 와샬로 풀었다.

노드가 최대 200개 이므로 충분히 해결할 수 있다.

 

우선 인접 행렬로 구성했다.

배열[a][b] = [b,c]

a->b로 가는 최단 경로중 b를 가장 먼저 들러야하고 비용은 c이다 는 의미이다.

처음 입력은 저런식으로 초기화 해준다.

배열[b][a] = [a,c] 반대로 초기화 해주면 된다.

 

다음 플로이드 와샬을 돌리자.

작은 값으로 갱신할 때 배열[i][k] + 배열[k][j] 의 값으로 보통 바꿀 것이다.

이때 [i][k]가 더 먼저 방문한 노드가 된다.

 

from sys import stdin

input = stdin.readline

n,m = map(int, input().split())
INF = 9876543210
adj_mat = [[[INF,INF] for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    a,b,c = map(int, input().split())
    adj_mat[a][b] = [b,c]
    adj_mat[b][a] = [a,c]

def solv():
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if i == j:
                    adj_mat[i][j][0] = -1
                else:
                    if adj_mat[i][j][1] > adj_mat[i][k][1] + adj_mat[k][j][1]:
                        adj_mat[i][j] =[adj_mat[i][k][0], adj_mat[i][k][1] + adj_mat[k][j][1]]

    for row in adj_mat[1:]:
        for before,cost in row[1:]:
            if before == -1:
                print('-',end=' ')
            else:
                print(before,end=' ')
        print()

solv()