[플로이드워셜] 11404번 - 플로이드 - python, 골드4

 

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

11404번: 플로이드

 

 

플로이드 개념 공부+코드이해를 하자마자 대놓고 똑같은 문제여서 그냥 복습이 바로 된 느낌이다.

 

특수한 개념은 없지만 고려해야할점은

 

0. 도시 == 노드, 버스 == 간선이라는 것을 알고

1. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. >> 이걸 잘 처리해주면 되는 문제! 

(예제 입력을 보면 1에서 4로가는 간선이 여러개가 있었다)

2. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. >> 마지막에 INF이면 0출력

 

 

💻 내가 쓴 정답 CODE

#플로이드 백준 11404 골드4

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

n = int(input()) #도시의 개수 (노드)
m = int(input()) #버스의 개수 (간선)

dist = [[INF]*n for _ in range(n)]

for i in range(n):
    dist[i][i] = 0

for _ in range(m) :
    start, end, cost = map(int,input().split())
    if dist[start-1][end-1] > cost:
        dist[start-1][end-1] = cost

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


#출력
for i in range(n):
    for k in range(n):
        if(dist[i][k] == INF):
            print(0,end=' ')
        else: 
            print(dist[i][k], end=' ')
    print()

 

 

 

내일 플로이드 관련문제 하나 더 풀어보고

다익스트라 공부도 해야겠다.

 

내일 참고할 블로그!  

https://it-garden.tistory.com/241