[백준] 11404번: 플로이드

 

 

 

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

11404번: 플로이드

 

 

 

 

 

✅  Solution

• 모든 도시 간의 거리를 구하는 문제로, 플로이드 워셜 구현 문제이다. 
• ‼️ 주의 ‼️ 도시 i에서 도시 j로 가는 길은 한 개가 아니다. 여러 개 중에 최솟값을 넣어줘야 한다. 
  
  • 이걸 놓쳐서 계속 틀렸다. 문제 좀 잘 읽자.. TT

 

 

 

 

 

✅  Code

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
distance = [[1e9] * (n+1) for _ in range(n+1)] # 최댓값으로 초기화

for _ in range(m):
    a, b, c = map(int, input().split())
    distance[a][b] = min(distance[a][b], c) # 이미 있는 거리와 비교해서 최솟값 넣어주기 !!

# 출발지와 도착지가 같은 경우 0으로 
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            distance[i][j] = 0
            
# 비교하면서 값 업데이트
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(n+1):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

# 만약 갈 수 없다면 0으로
for i in range(1, n+1):
    for j in range(1, n+1):
        if distance[i][j] >= 1e9:
            distance[i][j] = 0
            
for i in range(1, n+1):
    for j in range(1, n+1):
        print(distance[i][j], end=' ')
    print()