#3891. [Usaco2014 Dec]Piggy Back

[Usaco2014 Dec]Piggy Back


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 BB units of energy when walking from a field to an adjacent field, and Elsie spends EE 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 PP units of energy (where PP might be considerably less than B+EB+E, the amount Bessie and Elsie would have spent individually walking to the adjacent field). If PP 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 PP 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,EB,E, and PP, as well as the layout of the farm, please compute the minimum amount of energy required for Bessie and Elsie to reach the barn.


给定一个 nn 个点 mm 条边的无向图,其中 Bessie 在 11 号点,Elsie 在 22 号点,它们的目的地为 nn 号点。Bessie 每经过一条边需要消耗 BB 点能量,Elsie 每经过一条边需要消耗 EE 点能量。当它们相遇时,它们可以一起行走,此时它们每经过一条边需要消耗 PP 点能量。求它们两个到达 nn 号点时最少消耗多少能量?


The first line of input contains the positive integers B,E,P,nB,E,P,n,and mm.BB,EE, and PP are described above. nn is the number of fields in the farm (numbered 1n1\dots n), and mm is the number of connections between fields. Bessie and Elsie start in fields 11 and 22, respectively. The barn resides in field nn. The next mm 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 11 to field nn, and field 22 to field nn, along a series of such connections.


A single integer specifying the minimum amount of energy Bessie and Elsie collectively need to spend to reach the barn.

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


In the example shown here, Bessie travels from 11 to 44 and Elsie travels from 22 to 33 to 44. Then, they travel together from 44 to 77 to 88.


对于 100%100\% 的数据,1B,E,P,m4×1041\le B,E,P,m\le 4\times 10^43n1043\le n \le 10^4