3176번 - 도로 네트워크 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB117934531300637.636%

문제

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.

다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

출력

총 K개 줄에 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

예제 입력 1 

5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2

예제 출력 1 

100 200
50 150
50 100

예제 입력 2 

7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5

예제 출력 2 

2 6
1 4
6 6
2 2
2 6

예제 입력 3 

9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3

예제 출력 3 

1 2
2 4
1 5
2 2
1 4
W3sicHJvYmxlbV9pZCI6IjMxNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBcdWFkZjggXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBOLTFcdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIzYzRcdWI4NWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHVhYzAwIFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMzMGRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QxZCBLXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkYyBcdWMzMGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1YyBcdWMwYzFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOLTFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBBLCBCLCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQVx1YzY0MCBCXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWUzOFx1Yzc3NFx1YWMwMCBDXHVjNzc4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgSyAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMTggRFx1YzY0MCBFXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gRFx1YzY0MCBFXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgS1x1YWMxYyBcdWM5MDRcdWM1ZDAmbmJzcDtEXHVjNjQwIEVcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibHViZW5pY2EiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB0cmFmZmljIG5ldHdvcmsgaW4gYSBjb3VudHJ5IGNvbnNpc3RzIG9mIE4gY2l0aWVzIChsYWJlbGVkIHdpdGggaW50ZWdlcnMgZnJvbSAxIHRvIE4pIGFuZCBOLTEgcm9hZHMgY29ubmVjdGluZyB0aGUgY2l0aWVzLiBUaGVyZSBpcyBhIHVuaXF1ZSBwYXRoIGJldHdlZW4gZWFjaCBwYWlyIG9mIGRpZmZlcmVudCBjaXRpZXMsIGFuZCB3ZSBrbm93IHRoZSBleGFjdCBsZW5ndGggb2YgZWFjaCByb2FkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsLCBmb3IgZWFjaCBvZiB0aGUgSyBnaXZlbiBwYWlycyBvZiBjaXRpZXMsIGZpbmQgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgcm9hZCBvbiB0aGUgcGF0aCBiZXR3ZWVuIHRoZSB0d28gY2l0aWVzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAyICZsZTsgTiAmbGU7IDEwMCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOLTEgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgQSwgQiBhbmQgQyBtZWFuaW5nIHRoYXQgdGhlcmUgaXMgYSByb2FkIG9mIGxlbmd0aCBDIGJldHdlZW4gY2l0eSBBIGFuZCBjaXR5IEIuIFRoZSBsZW5ndGggb2YgZWFjaCByb2FkIHdpbGwgYmUgYSBwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxIDAwMCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBLLCAxICZsZTsgSyAmbGU7IDEwMCAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgaW50ZWdlcnMgRCBhbmQgRSAmbmRhc2g7IHRoZSBsYWJlbHMgb2YgdGhlIHR3byBjaXRpZXMgY29uc3RpdHV0aW5nIG9uZSBxdWVyeS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5FYWNoIG9mIHRoZSBLIGxpbmVzIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0d28gaW50ZWdlcnMgJm5kYXNoOyB0aGUgbGVuZ3RocyBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uIGZvciB0aGUgY29ycmVzcG9uZGluZyBwYWlyIG9mIHRoZSBjaXRpZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Final Exam #2 2번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)