[파이썬] 11404번 '플로이드' 문제 풀이

[파이썬] 11404번 '플로이드' 문제 풀이

모든 노드 쌍에 대해 최단거리를 구하는 알고리즘으로는 플로이드-워셜 알고리즘이 있으며 이 알고리즘을 통해 문제를 해결합니다.

플로이드-워셜 알고리즘이란?

https://lbdiaryl.tistory.com/183?category=1015060

풀이

import sys INF = sys.maxsize n = int(input()) m = int(input()) Mat = [[INF] * n for _ in range(n)] for i in range(m): #초기 정보 입력 a, b, c = map(int, sys.stdin.readline().split()) if Mat[a - 1][b - 1] > c: Mat[a - 1][b - 1] = c for k in range(n): #각각의 노드를 지나는 경우와 거치지 않을 경우를 비교 후, 최솟값으로 초기화 for i in range(n): for j in range(n): if j == i: Mat[i][j] = 0 else: Mat[i][j] = min(Mat[i][j], Mat[i][k] + Mat[k][j]) for i in range(n): for j in range(n): if Mat[i][j] == INF: print(0, end=' ') else: print(Mat[i][j], end=' ') print()

문제 출처: https://www.acmicpc.net/problem/11404

from http://lbdiaryl.tistory.com/192 by ccl(A) rewrite - 2021-10-26 19:26:50