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. 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. 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. If P is very small, the most efficient solution may involve them meeting at a common field, then traveling together piggyback for the rest of the journey. Of course, if P is large, it may make more sense for them to travel separately.

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.

Line 1: The positive integers B, E, P, N, and M (all at most 40,000). N is the number of fields (numbered 1..N, N >= 3), and M is the number of connections. Bessie and Elsie start in fields 1 and 2 respectively. The barn is in field N.

Lines 2..1+M: Each describes a bi-directional connection between a pair of different fields, specified by their integer indices.

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

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Silver