산악 능선 횡단
골드 IV의견: 0
산악 지방에 \(N\)개의 마을과 \(M\)개의 양방향 산길이 있다. 각 산길은 두 마을을 잇고, 그 산길의 최대 고도차(양의 정수)가 등산 피로도로 기록되어 있다.
두 마을 사이의 이동 피로도는 해당 경로에 포함된 산길 피로도의 최댓값이다. 출발지와 목적지 사이에 여러 경로가 있을 때에는 이동 피로도를 최소화하는 경로를 선택한다.
모든 마을 쌍 \((i, j)\)에 대해 최솟값으로 최적화한 이동 피로도를 행렬로 출력하여라. 도달할 수 없는 쌍은 \(-1\)로 출력한다.
- \(1 \le N \le 100\)
- \(0 \le M \le \frac{N(N-1)}{2}\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10^9\)
첫째 줄에 마을 수 \(N\)과 산길 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 산길의 양 끝 마을 번호 \(u\), \(v\)와 피로도 \(w\)가 공백으로 구분되어 주어진다.
\(N\)개의 줄에 걸쳐 행렬을 출력한다. \(i\)번째 줄의 \(j\)번째 수는 마을 \(i\)에서 \(j\)까지의 최소 피로도이다. 도달 불가능하면 \(-1\)을 출력한다.
4 4
1 2 3
2 3 5
3 4 2
1 4 10
0 3 5 5
3 0 5 5
5 5 0 2
5 5 2 0
마을 \(1\)에서 \(3\)까지: 경로 \(1\!\to\!2\!\to\!3\)의 최대 고도차는 \(\max(3,5)=5\)이고, \(1\!\to\!4\!\to\!3\)은 \(\max(10,2)=10\)이다. 따라서 최솟값은 \(5\)이다.
3 3
1 2 7
2 3 2
1 3 9
0 7 7
7 0 2
7 2 0
마을 \(1\!\to\!3\): 직접(\(9\)) vs \(1\!\to\!2\!\to\!3\)(\(\max(7,2)=7\)). 최솟값 \(7\).
riseoj 작성
출처 Original
평가 및 의견
산악 능선 횡단
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
산악 능선 횡단