BOJ 11404 PS일기 - Floyd Warshall

요구사항

100개 이하 도시 10만개 이하 버스노선(이동비용)이 주어졌을 때, 모든 도시 간의 이동 비용의 최솟값을 구해야한다.

문제접근

플로이드와샬 알고리즘으로 v세제곱의 시간복잡도로 비용들을 구한다.

데이터 흐름

두 도시간의 비용을 2차원 배열 x,y로 대입시켜두고 x,y가 동일한 같은 도시면 0으로 초기화한다. 그리고 플로이드 와샬 3중 for문으로 두도시간의 비용을 갱신한다. for문이 종료되면 출력한다. 만약 갈수없는 경우(INF)면 명세서 대로 0으로 출력해준다.

n,m,*data = open(0)
n = int(n)
m = int(m)
inf = 2**99
bus = [[(inf if y != x else 0) for x in range(n + 1)] for y in range(n + 1)]

for info in data:
    city1,city2,cost = [*map(int, info.split(' '))]
    bus[city1][city2] = min(cost, bus[city1][city2])

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j])

for i in range(1, n + 1):
    answer = ' '.join([*map(lambda x: str(x) if x != inf else '0', bus[i][1:])])
    print(answer)