알고리즘
어려움
코딩
모든 쌍 최단 경로
플로이드-워셜로 모든 정점 간 최단 거리
30분
85점
1개 테스트케이스
#3741
문제 설명
N개의 정점과 M개의 간선이 있는 가중치 그래프에서 모든 정점 쌍 간의 최단 거리를 구하세요.
입력 형식
첫 줄: 정점 수 N, 간선 수 M
다음 M줄: 시작 도착 가중치
출력 형식
N x N 행렬 (i에서 j로의 최단 거리, 불가능하면 INF)
제약 조건
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ N²
- 가중치는 양수
시간 복잡도
O(N³)
예제 테스트케이스
예제 1
기본
입력
4 7 1 2 5 1 4 8 2 1 7 2 3 9 3 1 2 3 4 4 4 3 3
출력
0 5 11 8 7 0 9 12 2 7 0 4 5 10 3 0
실행 버튼을 눌러 코드를 실행하세요.