레이팅 미적용설명
\(n\)개의 도시와, 한 도시에서 출발하여 다른 도시에 도착하는 버스 \(m\)개가 있다. 모든 도시 쌍 \((A, B)\)에 대해, \(A\)에서 \(B\)로 가는 데 필요한 비용의 최솟값을 구하여라.
같은 구간을 운행하는 버스가 여러 개 있을 수 있다.
제약
\(1 \le n \le 100\), \(0 \le m \le 100\,000\), 비용은 \(100\,000\) 이하의 자연수이다.
입력 형식
첫째 줄에 도시의 개수 \(n\), 둘째 줄에 버스의 개수 \(m\)이 주어진다. 다음 \(m\)개의 줄에 버스 정보 \(a\ b\ c\) (출발, 도착, 비용)가 주어진다.
출력 형식
\(n\)개의 줄에 걸쳐, \(i\)번째 줄에 도시 \(i\)에서 각 도시 \(j\)로 가는 최소 비용을 공백으로 구분해 출력한다. 갈 수 없는 경우(\(i = j\) 포함)에는 \(0\)을 출력한다.
예제 1
입력
3
4
1 2 4
2 3 2
1 3 7
3 1 1
출력
0 4 6
3 0 2
1 5 0
설명
\(1 \to 3\)은 \(1 \to 2 \to 3 = 6\)이 직행(\(7\))보다 싸다.
예제 2
입력
2
1
1 2 9
출력
0 9
0 0
설명
\(2\)에서 \(1\)로는 갈 수 없으므로 \(0\)을 출력한다.
문제 정보
riseoj 작성
출처 Original
태그