알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 61. 가장 빠른 버스 노선 구하기

문제

n(2 <= n <= 100)개의 도시가 있다. 한 도시에서 출발해 다른 도시에 도착하는 m개의 버스가 있다. 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 관해 가는데 필요한 비용의 최솟값을 구하는 프로그램

n <= 100 / 출발, 도착 노드가 아님 -> 플로이드 워셜

 

코드

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())

# 인접 행렬로 선언
graph = [ [float('inf')] * (n+1) for _ in range(n+1)]

# 자기 자신으로 가는 경로는 0으로 설정
for i in range(1, n+1):
    graph[i][i] = 0

for i in range(m):
    start, end, weight = map(int, input().split())
    if graph[start][end] > weight:
        graph[start][end] = weight
    
for k in range(1, n+1):
    for s in range(1, n+1):
        for e in range(1, n+1):
            if graph[s][e] > graph[s][k] + graph[k][e]:
                graph[s][e] = graph[s][k] + graph[k][e]
            
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == float('inf'):
            print(0, end = ' ')
        else:
            print(graph[i][j], end=' ')
    print()

 

자기자신을 0으로 설정하는거 안해줬다가 몇번이나 틀림