R00756
플로이드
골드 IV레이팅
의견: 0
설명
\(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\)을 출력한다.
골드 III문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
플로이드
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
플로이드
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기