가장 덜 가파른 등산로
골드 IV의견: 0
한 국립공원에는 \(N\)개의 대피소가 \(M\)개의 등산로로 연결되어 있다. 등산로 \(i\)는 두 대피소 \(u_i, v_i\)를 잇고, 그 길의 최대 경사도는 \(h_i\)이다.
초보 등산객이 출발 대피소 \(S\)에서 목표 대피소 \(T\)까지 가려 한다. 한 경로의 "힘듦 정도"는 그 경로에서 지나는 등산로들의 최대 경사도로 정한다. 즉 경로 중 가장 가파른 구간이 그 경로의 힘듦 정도가 된다.
가능한 모든 경로 중에서 힘듦 정도(최대 경사도)가 가장 작은 경로를 택했을 때, 그 값을 구하여라. \(S\)에서 \(T\)로 가는 경로가 없으면 \(-1\)을 출력한다.
다중 등산로가 있을 수 있고, 자기 루프는 없다.
- \(2 \le N \le 100{,}000\)
- \(1 \le M \le 150{,}000\)
- \(1 \le u_i, v_i \le N\), \(u_i \ne v_i\)
- \(1 \le h_i \le 1{,}000{,}000\)
- \(1 \le S, T \le N\), \(S \ne T\)
첫째 줄에 \(N\ M\ S\ T\)가 주어진다.
다음 \(M\)개의 줄에 각 등산로의 정보 \(u_i\ v_i\ h_i\)가 주어진다.
\(S\)에서 \(T\)까지 갈 때 경로의 최대 경사도를 최소화한 값을 출력한다. 갈 수 없으면 \(-1\).
4 4 1 4
1 2 10
2 4 10
1 3 4
3 4 6
6\(1\to 3\to 4\) 경로의 최대 경사도는 \(\max(4,6)=6\)으로, \(1\to 2\to 4\)(최대 \(10\))보다 작다. 답은 \(6\).
4 2 1 4
1 2 3
3 4 3
-1\(1\)에서 \(4\)로 가는 경로가 없으므로 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
가장 덜 가파른 등산로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 덜 가파른 등산로