11404-백준-플로이드

1. 문제 출처

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

11404번: 플로이드

2. 풀이

모든 지점에서 다른 모든 지점까지의 최단경로를 계산하는 문제이다..

딱 플로이드 워셜(이름부터 플로이드 이다...)을 위한 문제이다.

플로이드 워셜의 점화식을 이용하였다.

Dab = min(Dab , Dak +Dka)

이를 코드로 표현하면 다음과 같다.

for k in range(n):
        for a in range(n): 
            for b in range(n):
            	D[a][b] = min(D[a][b], D[a][k]+D[k][b])

문제 정답

# 입력
n = int(input())
bus_count = int(input())
# 무한인 값으로 cost값 초기화
cost_list = [[float("inf")]*n for _ in range(n)]

for _ in range(bus_count):
    # 비용이 최소값인 값을 저장
    start_city,end_city,cost = map(int,input().split())
    cost_list[start_city-1][end_city-1] = min(cost,cost_list[start_city-1][end_city-1])

#플로이드 워셜 알고리즘 이용 O(n**3)의 시간 복잡도를 가지고 있디...
def solution():
    # temp_city 는 중간에 경유하는 도시를 뜻한다.
    for temp_city  in range(n):
        for start_city in range(n): 
            for end_city in range(n):
                # 시작 도시와 끝도시가 같다면 0으로 해준다.
                if start_city == end_city:
                    cost_list[start_city][end_city] = 0
                else :
                    cost_list[start_city][end_city] = \
                    min(cost_list[start_city][end_city], cost_list[start_city][temp_city]+cost_list[temp_city][end_city])
    # 출력
    for row in cost_list:
        for cell in row:
            if cell == float("inf"):
                print(0,end = " ")
            else:
                print(cell, end = " ")
        print()
            
                
solution()

플로이드 워셜