소들의 장애물 넘기 > 문제은행

본문 바로가기


실전대비 Level5

1494 : 소들의 장애물 넘기

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 22 회    시도횟수: 55 회   



농부인 창호는 기르고 있는 소들이 나라에서 주최하는 장애물 뛰어넘기 대회를 준비하길 원하기 때문에, 소들은 장애물을 뛰어 넘는 연습을 하는 중이다. 너무나 연습을 많이 한 나머지 소들은 모두 지쳤고, 가능한 한 최소한의 에너지를 사용해서 장애물을 넘기를 원한다.

 

작은 높이의 장애물을 넘는 것은 쉽지만, 높은 높이의 장애물을 넘는 것은 장애물이 높을수록 어려워지고 그만큼 소들에게 스트레스를 준다. 따라서, 소들은 넘어야 하는 가장 높은 높이를 가진 장애물에 대해서만 생각하고자 한다.

 

소들의 연습방은 N(1≤N≤300)개의 위치로 이루어져 있고 각각의 위치엔 1부터 N의 숫자가 명시되어 있다. 그리고 M(1≤M≤25,000)개의 두 개의 위치사이에 대한 단방향 경로가 주어진다. 경로 또한 1부터 M으로 명시가 된다.

 

i번째 경로는 경로가 시작하는 위치 Si 그리고 경로의 도착 위치 Ei, 그리고 그 사이에 존재하는 장애물 Hi(1≤Hi≤1,000,000)가 주어진다. 경로 사이에는 반드시 하나의 장애물만 존재하며, 소들이 이동할 때 거치게 되는 경로에 존재하는 장애물은 반드시 넘어야 한다.

 

소들은 T(1≤T≤40,000)개의 연습을 마쳐야 한다. i번째의 연습은 2개의 숫자 Ai, Bi (1≤Ai, Bi≤N)로 주어지는데, 이는 소들이 Ai의 위치에서 Bi의 위치로 이동하는 연습을 해야 한다는 것이다. 소들은 Ai부터 Bi까지 뛰어 넘게 되는 최대 높이의 장애물이 최소한 낮은 높이기를 희망한다. 이를 알아보는 프로그램을 작성하라.


입력의 첫 번째 줄에는 N, M, T 세 개의 숫자가 공백을 사이에 두고 주어진다.
두 번째 줄에서 M+1번째 줄까지는 M개의 경로가 주어지는데, i+1번째 줄에는 i번째 경로에 대한 Si, Ei, Hi가 공백을 사이에 되고 주어진다.
M+2번째 줄부터, M+T+1번째 줄에는 T개의 연습이 주어지는데, i+M+1번째 줄에는 i번째 연습에 대한 Ai와 Bi가 공백을 사이에 두고 주어진다.


각각의 줄에는 i번째 연습에 대해서 넘게 되는 최대 높이의 장애물이 최소가 되는 경우에 대한 높이를 출력한다.
이동할 수 없는 경우는 -1를 출력한다.

[Copy]
5 6 3 
1 2 12 
3 2 8 
1 3 5 
2 5 3 
3 4 4 
2 4 8 
3 4 
1 2 
5 1
[Copy]
4
8 
-1





USACO 2007 November Silver Cow Hurdles, poj 3615

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.