[BOJ] Q11404 플로이드

[BOJ] Q11404 연구소

Question

Language: Python

Difficulty: Gold 4

문제의 취지는 노드 a 에서 노드 b로 가는 최소 경로를 구하는 문제인데, a,b가 정해진 게 아닌 모든 노드에 대해서 적용해야하는 ASSP(All Source Shortest Path) 문제이다. –> Floyd-Warshall 알고리즘을 이용해서 풀이하면 된다. 단, a->b 간에 간선이 여러 개가 있을 수 있으니 가장 짧은 거리의 간선만 추가할 수 있도록 한다.

Solution

from math import inf

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

if __name__ =="__main__:
  v,e=0,0
  graph=[]

  v=int(input())
  e=int(input())
  graph=[[math.inf for _ in range(v+1)] for _ in range(v+1)]
  for i in range(1,v+1):
      for j in range(1,v+1):
        if i==j:
          graph[i][j]=0

  for _ in range(e):
      v1,v2,cost=map(int,input().split())
      if cost<graph[v1][v2]:
          graph[v1][v2]=cost

      
  floyd_warshall(v,graph)

  for i in range(1,v+1):
      for j in range(1,v+1):
          if graph[i][j]==inf:
              graph[i][j]=0
          print(graph[i][j],end=" ")
      print()