이해

• n개의 도시가 주어지고, 한 도시에서 다른 도시에 도착하는 m개의 버스가 있다.
• 각 버스는 한 번 사용할 때 필요한 비용이 있고 한 도시와 다른 한 도시로 가는 버스는 하나 이상이다.
• 모든 도시의 쌍에 대해서 도시 A에서 B로 가는데 필요한비용의 최솟값을 출력하라.

계획

• 도시를 그래프의 노드로 보고, 도시 A -> 도시 B로 가는 버스를 사용할 때 필요한 비용이 c일 때 노드 A -> 노드 B로의 가중치 c인 간선으로 볼 때 모든 노드 -> 모든 노드로 가는 최단 거리를 구해준다.
• 최단거리는 플로이드워셜 알고리즘을 사용한다.

실행

INF = int(1e9)
n = int(input())
k = int(input())
distance = [[INF] * n for _ in range(int(n))]
for i in range(n):
    distance[i][i] = 0

for _ in range(k):
    a, b, w = map(int, input().split())
    if distance[a - 1][b - 1] > w:
        distance[a - 1][b - 1] = w
for k in range(n):
    for a in range(n):
        for b in range(n):
            distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])

for i in range(n):
    print(" ".join(map(str, distance[i])).replace(str(INF), "0"))

개선

• 딱히 없다.

회고

• 쉬웠다.