플로이드

면접 대비

시간 제한1초메모리 제한256 MB

요약

최대 100,000개 버스 노선으로 n개 도시의 모든 순서쌍을 잇는 가장 싼 요금을 구하고 도달할 수 없으면 0을 출력합니다.

난이도: 보통10점 중 4점
유형: 최단 경로, 그래프, 동적 계획법
정답자: 아직 제출이 없습니다

문제

n(2 ≤ n ≤ 100)개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착하는 버스가 m(1 ≤ m ≤ 100,000)개 있다. 버스마다 한 번 타는 데 드는 비용이 정해져 있다.

모든 도시 쌍 (A, B)에 대해 도시 A에서 도시 B로 가는 데 드는 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n, 둘째 줄에 버스의 개수 m이 주어진다. 셋째 줄부터 m+2번째 줄까지 버스 정보가 한 줄에 하나씩 주어진다. 각 줄은 버스의 시작 도시 a, 도착 도시 b, 한 번 타는 데 드는 비용 c로 이루어진다. 시작 도시와 도착 도시가 같은 버스는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

같은 시작 도시와 도착 도시를 잇는 노선이 하나가 아닐 수 있다.

출력

n개의 줄을 출력한다. i번째 줄의 j번째 숫자는 도시 i에서 도시 j로 가는 데 드는 최소 비용이다. i에서 j로 갈 수 없으면 그 자리에 0을 출력한다. 한 줄에 있는 숫자는 공백 하나로 구분한다.

예제3

예제 1

입력

예상 출력

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

예제 2
입력
```
2
1
1 2 5
```
예상 출력
```
0 5
0 0
```
예제 3
입력
```
2
3
1 2 7
2 1 3
1 2 4
```
예상 출력
```
0 4
3 0
```