레이팅 미적용베시와 여동생 엘시는 낮 동안 서로 다른 목초지에서 풀을 뜯고, 저녁이 되면 둘 다 헛간으로 걸어 돌아가 쉬고 싶어 한다. 둘은 걷는 동안 소모하는 에너지의 총합을 최소화할 계획을 세운다.
베시는 한 목초지에서 인접한 목초지로 이동할 때 B 단위의 에너지를 소모하고, 엘시는 E 단위를 소모한다. 하지만 베시와 엘시가 같은 목초지에 함께 있으면 베시가 엘시를 어깨에 업고 P 단위의 에너지만 소모하면서 함께 인접한 목초지로 이동할 수 있다. P가 매우 작다면, 둘이 어떤 목초지에서 만난 뒤 남은 여정을 업은 채로 함께 이동하는 것이 가장 효율적인 방법일 수 있다. 물론 P가 크다면 따로 이동하는 편이 더 나을 수도 있다.
B, E, P와 농장의 구조가 주어질 때, 베시와 엘시가 헛간에 도착하는 데 필요한 최소 에너지를 계산하시오.
첫째 줄에 양의 정수 B, E, P, N, M이 주어진다 (모두 40,000 이하). N은 목초지의 수이고 (1..N번으로 번호가 매겨지며, N >= 3), M은 연결의 수이다. 베시와 엘시는 각각 목초지 1과 2에서 출발한다. 헛간은 목초지 N에 있다.
둘째 줄부터 1+M번째 줄까지 각 줄에는 서로 다른 두 목초지 사이의 양방향 연결이 두 목초지의 정수 번호로 주어진다.
베시와 엘시가 헛간에 도착하기 위해 함께 소모해야 하는 최소 에너지를 나타내는 정수 하나를 출력한다.
piggyback.in · 출력을 쓸 파일 piggyback.out4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 822Output details: Bessie goes 1->4, Elsie goes 2->3->4, then they travel together 4->7->8.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Silver