[백준] 11404번 플로이드(python)

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

11404번: 플로이드

1. 난이도 골드4 (🥇) 

 

2. 문제 해결 방법

문제의 이름에서 보이듯 이 문제는 플로이드 워셜 알고리즘을 사용해야 한다.

 

그러나 이 문제는 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 라는 함정이 있다.

 

테스트 케이스를 살펴보면

 

1 4 1

1 4 2 

 

와 같이 1에서 4로 가는 노선이 두 개가 있는데, 뒤에 오는 값인 graph[1][4] = 2가 들어가게 되고, 이는 최단경로가 아니다.

 

따라서 graph에 원소를 넣을 때, 기존의 값과 새로 들어오는 가중치 중 최솟값을 찾아서 넣어야한다.

 

for i in range(m):
  a,b,c = map(int, input().rstrip().split()) #a시작,b도착,c비용
  graph[a][b] = min(graph[a][b],c)

 

3. 내가 작성한 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip()) #도시
m = int(input().rstrip()) #버스

INF = int(1e9)

graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1,n+1):
  for b in range(1,n+1):
    if a==b:
      graph[a][b] = 0

for i in range(m):
  a,b,c = map(int, input().rstrip().split()) #a시작,b도착,c비용
  graph[a][b] = min(graph[a][b],c)

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

for a in range(1,n+1):
  for b in range(1,n+1):
    if graph[a][b] == INF:
      print(0, end = " ")
    else:
      print(graph[a][b], end = " ")
  print()