황금 네트워크
골드 II의견: 0
마법사 왕국에는 \(N\)개의 도시와 \(M\)개의 도로가 있다. 각 도로는 두 도시를 잇고 통행 비용이 있다. 배달부는 한 경로를 이동할 때, 그 경로에 포함된 도로들 중 가장 비싼 도로의 비용만 지불한다.
\(Q\)개의 쿼리가 주어진다. 각 쿼리 \((s, t)\)에 대해, 도시 \(s\)에서 도시 \(t\)로 가는 경로 중 지불 비용을 최소화한 값을 출력하여라.
그래프는 연결되어 있다.
- \(2 \le N \le 200\,000\)
- \(N-1 \le M \le 300\,000\)
- \(1 \le Q \le 200\,000\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10^9\)
- 그래프는 연결되어 있다.
- 각 쿼리에서 \(s \ne t\)이다.
첫째 줄에 도시의 수 \(N\), 도로의 수 \(M\), 쿼리의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 각 도로의 양 끝 도시 \(u\), \(v\)와 비용 \(w\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 쿼리 \(s\), \(t\)가 공백으로 구분되어 주어진다. \(s \ne t\)가 보장된다.
\(Q\)개의 줄에 걸쳐, 각 쿼리의 최소화된 최대 간선 비용을 출력한다.
5 6 3
1 2 3
2 3 1
3 4 4
4 5 2
1 3 6
2 4 5
1 4
2 5
1 5
4
4
4
MST는 간선 (2-3:비용1), (4-5:비용2), (1-2:비용3), (3-4:비용4)로 구성된다. 경로 \(1\to4\): \(1-2-3-4\), 최대 비용 \(4\). 경로 \(2\to5\): \(2-3-4-5\), 최대 \(4\). 경로 \(1\to5\): \(1-2-3-4-5\), 최대 \(4\).
4 5 3
1 2 1
2 3 2
3 4 3
1 3 4
2 4 5
1 4
1 3
2 4
3
2
3
MST는 (1-2:1),(2-3:2),(3-4:3)이다. 경로 \(1\to4\): 최대 \(3\), 경로 \(1\to3\): 최대 \(2\), 경로 \(2\to4\): 최대 \(3\).
riseoj 작성
출처 Original
평가 및 의견
황금 네트워크
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
황금 네트워크