비 피하기 (takeshelter) > 문제은행

본문 바로가기


실전대비 Level5

1493 : 비 피하기 (takeshelter)

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



농부 창호는 소들이 비에 젖는 걸 너무나도 싫어해서, 농장에 언제 비가 오는지 알려주는 사이렌을 설치했다. 

소들은 비가 오기 전에 대피 작전을 세워서 한 마리의 소도 빠짐 없이 모두 헛간 안으로 대피하려고 한다. 

하지만 불행하게도 일기예보가 자주 틀려서 난감한 일이 발생되곤 한다. 

비가 오지도 않는데 사이렌을 울리는 일을 최대한 줄이고, 소들이 대피할 시간을 미리 충분히 파악하여 가능한 한 사이렌을 늦게 울리려고 한다. 

농장에는 N개의 목초지가 있고 목초지에는 소들이 대피할 수 있는 헛간이 세워진 곳도 있다. 

헛간은 크기가 제한되어 있어서 한 헛간에 모든 소들이 들어가지 못할 수도 있으며 목초지에서 헛간으로 들어가거나 나오는 데에는 시간이 걸리지 않는다.

 

목초지 사이에는 소들이 이동할 수 있는 M개의 길이 있고 그 길들은 매우 넓어서 아무리 많은 소들도 한꺼번에 마음껏 양방향으로 이동할 수 있다.

 

창호를 위해 모든 소들이 헛간으로 대피할 때까지 걸리는 최소 시간을 구하는 프로그램을 작성해 주자.


첫 줄에 N(1≤N≤200)와 M(1≤M≤1500)가 주어진다.

이후 N개의 줄에는 각 목초지의 상태를 나타내는 두 개의 정수가 입력된다. 첫 번째 수는 현재 목초지에 있는 소들의 수(0 이상 1000 이하)이며, 두 번째 수는 그 목초지에 설치된 헛간 안에 들어갈 수 있는 소의 최대 수(0 이상 1000 이하)이다. 만약 이 수가 0이라면 헛간이 없다는 것을 의미한다. 목초지의 번호는 입력되는 순서대로 1부터 N까지 매겨진다.

다음부터 M개의 줄에는 길의 정보를 나타내는 세 개의 정수 s, e, dis 가 입력된다. s와 e는 (1 ≤ s, e ≤ N)는 목초지의 번호를 나타내며, dis는(1 ≤ dis ≤ 10억) 목초지 s에서 목초지 e로 이동하는데 걸리는 시간을 의미한다. 모든 길은 양방향으로 이동이 가능하며 동일한 입력이 있을 때에는 유리한 것으로 적용한다.


모든 소들이 헛간으로 대피할 때까지 걸리는 최소 시간을 출력한다. 만일 모든 소들이 대피할 수 있는 방법이 없다면 -1을 출력한다.

[Copy]
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
[Copy]
110



1번 목초지에 있는 7마리의 소 중 2마리는 1번 헛간에, 4마리는 2번 헛간에, 1마리는 3번 헛간에 들어간다. 
3번 목초지에 있던 소 2마리는 3번 헛간에 들어가면 된다. 
이 때 1번 목초지에서 3번 목초지의 헛간으로 이동하는 시간이 110으로 가장 최소시간이며 이보다 더 빨리 모든 소들을 대피시키는 방법은 없다.





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.