[Python]최단경로 백준 11404

   문제

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

이전 다익스트라 알고리즘이나 벨만포드 알고리즘은 하나의 노드에서 갈수있는 최소거

리를 구하는 문제였다면이번엔 모든 노드에서 모든노드로 갈수있는 최소거리를 모두 

구하는 문제이다.

위 알고리즘들을 사용했을시에는 O(EV^2)이라는 시간이 걸릴것이다.

새로운 방법을 써야하는데 플로이드 워셜 알고리즘이다.

코드는 간단한 편이며 DP라고 볼수도 있겠다.

시간복잡도는 O(EV)이다.

https://mygumi.tistory.com/110

위 사이트가 이해하기 제일 쉬웠던거 같다.

import sys
 
n=int(sys.stdin.readline())
m=int(sys.stdin.readline())
INF=sys.maxsize
G=[[INF for _ in range(n+1)] for _ in range(n+1)]
 
for _ in range(m):
    a,b,c=map(int,sys.stdin.readline().split())#출발 도착 비용
    G[a][b]=min(c,G[a][b])#입력보다 더 짧은 노선이 있다면
 
 
for k in range(1,n+1):#플로이드 워샬
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i==j:
                G[i][j]=0
            else:
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])
 
for i in range(1,n+1):
    for j in range(1,n+1):
        if G[i][j]==INF:#경로가 없을시 0으로
           print(0,end=" ")
        else:
           print(G[i][j],end=" ")
    print()