[백준 11404번 파이썬] 플로이드

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

11404번: 플로이드

1.아이디어

-모든점-> 모든점 : 플로이드 문제

-비용배열

-간선의 비용 대입

-거쳐서 비용 줄어들 경우, 갱신 ( for문 3번)

 

2. 시간 복잡도 (for문 3번)

-플로이드 :O(V^3)  ( V=간선의  갯수)

 

3. 변수

-비용배열 

 

 

 

 

import sys
input = sys.stdin.readline
INF = sys.maxsize

n=int(input())
m=int(input())
rs=[[INF]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
  rs[i][i]=0               #자기자신으로 가는건 0으로 초기화
for i in range(m):
  a,b,c=map(int,input().split())
  rs[a][b]=min(rs[a][b],c)  #a에서 b까지 가는 방법이 많다. 그중에서 min값을 넣어준다.

#j에서 i까지 가는데 k를 거친다.

for k in range(1,n+1):
  for j in range(1,n+1):
    for i in range(1,n+1):
      if rs[j][i]>rs[j][k]+rs[k][i]:
         rs[j][i]=rs[j][k]+rs[k][i]

for j in range(1,n+1):
  for i in range(1,n+1):
    if rs[j][i]==INF: print(0,end=' ')
    else: print(rs[j][i], end =' ')
  print()