2350번 - 대운하 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 231 | 112 | 83 | 53.205% |
문제
4대강 사업의 성공에 힘입은 정부는 대한민국의 도시들을 모두 운하로 연결하여 뱃길로 KTX를 대체하려는 계획을 세웠다.
대한민국에는 N개의 도시가 있고, 이들을 연결하는 M개의 운하를 건설하려고 한다. 하지만 지형의 문제로 운하의 폭을 제한할 수 밖에 없었기 때문에, 문제가 생겼다. 배의 폭이 운하의 폭보다 작거나 같아야 운하를 무사히 통과할 수 있기 때문이다.
정부는 K개의 노선을 준비했다. 각 노선의 도시 i와 j간을 운행하는 배는 도시 i와 j 간의 경로에 포함되는 운하를 통과할 수 있어야 한다. (이 경로는 여러 개가 존재할 수 있다.) 배가 클수록 많은 사람을 실을 수 있으므로, 정부는 배의 폭을 최대화하기를 원한다.
N개의 도시는 운하로 서로 연결되어 있음이 보장되며, 운하는 양방향으로 통행이 가능하다.
입력
입력의 첫 번째 줄에는 도시의 수 N, 운하의 수 M, 노선의 수 K가 주어진다. (N ≤ 1000, M ≤ 100000, K ≤ 10000)
다음 M개의 줄에는 세 정수 i, j, w가 주어지며, 이는 도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미한다. (1 ≤ i, j ≤ N, w ≤ 200)
다음 K개의 줄에는 각 노선이 연결하는 도시 i, j가 주어진다. (1 ≤ i, j ≤N)
출력
K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력한다.
예제 입력 1
6 9 4 1 2 2 1 4 3 1 6 1 2 3 3 2 5 2 3 4 4 3 6 2 4 5 5 5 6 4 2 6 3 5 1 2 4 6
예제 출력 1
3 4 3 4
출처
Olympiad > International Autumn Tournament in Informatics > 2012 > Group A (Seniors) 2번
- 문제를 번역한 사람: inhibitor
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호