백준비단뱀 11404호: 플로이드

by

https://www.acmicpc.net/problem/11404

11404호: 플로이드

첫 번째 줄에는 도시의 수 n이, 두 번째 줄에는 버스의 수 m이 주어집니다. 그리고 세 번째 라인에서 m+2 라인까지는 다음과 같은 버스 정보가 주어진다. 먼저 버스의 출발 도시 번호는

'추천 관련글,

www.acmicpc.net


import sys

sys.stdin = open('C:/Users/USER/Desktop/vs/py/py1/input.txt', 'r')


def input():
    return sys.stdin.readline().strip()

# ==================================================================================


INF = float('inf')  # 충분히 큰 수

city_num = int(input())  # 도시(정점) 수
bus_num = int(input())  # 버스(간선) 수

bus_list = ((INF for __ in range(city_num+1)) for _ in range(city_num+1))

for i in range(1, city_num+1):
    bus_list(i)(i) = 0

for _ in range(bus_num):  # 버스 정보 입력
    st, ed, cost = map(int, input().split())
    bus_list(st)(ed) = min(cost, bus_list(st)(ed))


for i in range(1, city_num+1):  # 플로이드
    for a in range(1, city_num+1):
        for b in range(1, city_num+1):
            bus_list(a)(b) = min(bus_list(a)(b), bus_list(a)(i)+bus_list(i)(b))

for i in range(1, city_num+1):  # 출력
    for j in range(1, city_num+1):
        num = bus_list(i)(j)
        if num == INF:
            num = 0
        print(num, end=' ')
    print()

그냥 플로이드의 알고리즘