2021.2.26 [백준] 플로이드

플로이드 워셜 알고리즘

 

 

Q

 

www.acmicpc.net/problem/11404

11404번: 플로이드

 

A

 

최단경로 문제여서 플로이드 워셜을 사용하여 풀었다. 주의할 점은 시작도시에서 도착도시로 가는 버스가 하나 이상 있을 수 있다는 점을 고려해서 문제를 푸는 것이였다.

참고로 input을 써서 풀었을 때 4860 ms 였지만, sys를 이용해서 풀었을 때 908 ms 였다.

귀찮더라도 sys 이용하자

 

코드

 

import sys

INF = int(1e9)

n = int(sys.stdin.readline().rstrip())

m = int(sys.stdin.readline().rstrip())

graph = [[INF] * (n+1) for _ in range(n+1)] #INF를 하는 이유는 최단경로이기때문, 0으로 해버리면 최단경로 설정 못함

 

for _ in range(m): 

    a, b, c = map(int, sys.stdin.readline().rstrip().split())

    graph[a][b] = min(graph[a][b], c) #시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 점을 고려

 

for k in range(1, n+1): #점화식 실행
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i != j and i != k and k != j: #자기에서 자기로 가는 것 제외시키기
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
       
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] >= INF: #자기에서 자기로 가는 것은 0 처리하기
            print(0, end = ' ')
        else:
            print(graph[i][j], end = ' ')
    print() #줄넘김을 위해서