# 3891: [Usaco2014 Dec]Piggy Back

## 3891: [Usaco2014 Dec]Piggy Back

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 116  Solved: 92

[Submit][Status][Discuss]

## Description

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.

## Input

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.

## Output

A single integer specifying the minimum amount of energy Bessie and

Elsie collectively need to spend to reach the barn.  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.

## Sample Input

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

22

## Source

Silver

（PS：程序里面我很逗比的还弄了个b作为反向map，实际上完全不必，一开始我没发现这个是无向图，所以b用来存储反向图，后来才发现我想多了TT）

``` 1 /**************************************************************
2     Problem: 3891
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:196 ms
7     Memory:6608 kb
8 ****************************************************************/
9
10 type
11     point=^node;
12     node=record
13                g,w:longint;
14                next:point;
15     end;
16     map=array[0..50000] of point;
17     arr=array[0..50000] of longint;
18 var
19    i,j,k,l,m,n,a1,a2,a3:longint;
20    a,b:map;
21    c,e,f,g:arr;
22    d:array[0..1000000] of longint;
23 function min(x,y:longint):longint;inline;
24          begin
25               if x<y then min:=x else min:=y;
26          end;
27 function max(x,y:longint):longint;inline;
28          begin
29               if x>y then max:=x else max:=y;
30          end;
32           var p:point;
33           begin
34                new(p);p^.g:=y;p^.w:=z;
35                p^.next:=a[x];a[x]:=p;
36           end;
37 procedure spfa(x:longint;a:map;var c:arr);inline;
38           var f,r:longint;p:point;
39           begin
40                fillchar(g,sizeof(g),0);
41                fillchar(c,sizeof(c),0);
42                f:=1;r:=2;d[1]:=x;g[x]:=1;c[x]:=1;
43                while f<r do
44                      begin
45                           p:=a[d[f]];
46                           while p<>nil do
47                                 begin
48                                      if (c[p^.g]=0) or((c[p^.g]>0) and (c[p^.g]>(c[d[f]]+p^.w))) then
49                                         begin
50                                              c[p^.g]:=c[d[f]]+p^.w;
51                                              if g[p^.g]=0 then
52                                                 begin
53                                                      g[p^.g]:=1;
54                                                      d[r]:=p^.g;
55                                                      inc(r);
56                                                 end;
57                                         end;
58                                      p:=p^.next;
59                                 end;
60                           g[d[f]]:=0;
61                           inc(f);
62                      end;
63                for i:=1 to n do dec(c[i]);
64           end;
65
66 begin
68      for i:=1 to n do a[i]:=nil;
69      for i:=1 to n do b[i]:=nil;
70      for i:=1 to m do
71          begin
75          end;
76      spfa(1,a,c);
77      spfa(2,a,e);
78      spfa(n,a,f);
79      l:=maxlongint;
80      for i:=1 to n do
81          if (c[i]<>-1) and (e[i]<>-1) and (f[i]<>-1) then
82             l:=min(l,a1*c[i]+a2*e[i]+a3*f[i]);
83      writeln(l);
84 end.```

251 篇文章37 人订阅

0 条评论

382100

34730

20940

31150

17400

12020

22100

55170

9620

34840