https://acmicpc.net/problem/1719

풀이

#플로이드워셜

전체 경로에 대한 비용을 구해야 하기 때문에 플로이드 워셜을 사용했다. 집하장의 개수인 n이 최대 200이기 때문에 플로이드 워셜을 사용해도 될 것이라고 판단했다.
경로 중 가장 처음의 집하장을 찾는 과정이 좀 헷갈렸는데 비용을 계산할 때 출발점부터 도착지까지의 집하장을 출발점부터 경유지의 집하장(path)로 업데이트 해주는 식으로 풀었다. path를 초기화할 때는 한 hop만큼 떨어져있는 집하장이 저장되기 때문에 이런 식으로 저장하면 경로 중에 가장 가까운 경로를 구할 수 있다.

import sys

# 플로이드워셜
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())

INF = sys.maxsize
graph = [[INF]*(n+1) for _ in range(n+1)]
path = [[0]*(n+1) for _ in range(n+1)]

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

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

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            new_cost = graph[i][k]+graph[k][j]
            if new_cost < graph[i][j]:
                graph[i][j] = new_cost
                path[i][j] = path[i][k] # 출발점에서 가장 앞의 집하장을 저장해주기 위해 앞부분의 집하장 저장


for i in path[1:]:
    for j in i[1:]:
        if j==0:
            print('-', end=' ')
        else:
            print(j, end=' ')
    print()