ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 C: Piggyback

内存限制：128 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：22 通过：12
返回比赛提交提交记录

题目描述

Problem 1: Piggy Back [Brian Dean, 2014] Bessie and her sister Elsie graze in different fields during the day, and in the evening they both want to walk back to the barn to rest. Being clever bovines, they come up with a plan to minimize the total amount of energy they both spend while walking. 
Bessie spends B units of energy when walking from a field to an adjacent field, and Elsie spends E units of energy when she walks to an adjacent field. However, if Bessie and Elsie are together in the same field, Bessie can carry Elsie on her shoulders and both can move to an adjacent field while spending only P units of energy (where P might be considerably less than B+E, the amount Bessie and Elsie would have spent individually walking to the adjacent field). If P is very small, the most energy-efficient solution may involve Bessie and Elsie traveling to a common meeting field, then traveling together piggyback for the rest of the journey to the barn. Of course, if P is large, it may still make the most sense for Bessie and Elsie to travel separately. On a side note, Bessie and Elsie are both unhappy with the term "piggyback", as they don't see why the pigs on the farm should deserve all the credit for this remarkable form of transportation.
Given B, E, and P, as well as the layout of the farm, please compute the minimum amount of energy required for Bessie and Elsie to reach the barn. 
题目描述

Bessie 和 Elsie 在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie 要花费 B 单位的能量，Elsie要花费 E 单位的能量。
如果某次他们两走到同一个区域，Bessie 可以背着 Elsie 走路，花费 P 单位的能量走到另外一个相连的区域。当然，存在 P>B+E 的情况。
相遇后，他们可以一直背着走，也可以独立分开。
Bessie 从 1 号区域出发，Elsie 从 2 号区域出发，两个人都要返回到位于 n 号区域的谷仓。

输入格式

The first line of input contains the positive integers B, E, P, N, and M. All of these are at most 40,000. B, E, and P are described above. N is the number of fields in the farm (numbered 1..N, where N >= 3), and M is the number of connections between fields. Bessie and Elsie start in fields 1 and 2, respectively. The barn resides in field N.  
The next M lines in the input each describe a connection between a pair of different fields, specified by the integer indices of the two fields. Connections are bi-directional. It is always possible to travel from field 1 to field N, and field 2 to field N, along a series of such connections.
第一行输入 5 个整数 B, E, P, n, m。B, E, P 的含义如上文所述。 n 表示农场中区域的数量，m 表示连接两个区域的道路的数量。
接下来 m 行，每行两个整数 x, y，描述一条 x 区域和 y 区域之间的双向边。数据保证图是连通的。  

输出格式

A single integer specifying the minimum amount of energy Bessie and Elsie collectively need to spend to reach the barn. 
一行一个整数，表示 Bessie 和 Elsie 能量花费总和的最小值。

输入样例 复制 

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

输出样例 复制 

22 ​

数据范围与提示

In the example shown here, Bessie travels from 1 to 4 and Elsie travels from 2 to 3 to 4. Then, they travel together from 4 to 7 to 8.
Bessie 从 1 走到 4，Elsie 从 2 走到 3 再走到 4。然后，两个人一起从 4 走到 7，再走到 8。



分类标签