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.

给定一个N个点M条边的无向图,其中Bessie在1号点,Elsie在2号点,它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量,Elsie每经过一条边需要消耗E点能量。当它们相遇时,它们可以一起行走,此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量?

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

Sample Output

22

HINT

Source

Silver

题解:直接求出1、2、n点到各点的距离(由于是无向图所以方向神马的直接无视之),然后枚举各个汇合点,然后计算各个点的代价,然后输出,然后AC

一开始在怀疑这样子是否一定可行,是否会存在两者会合后再次分开的可能,但实际上,如果两个人一起行动更合适的话,那么相遇就不需要再分离;如果两个人不适合一起行动的话,那么干脆就不需要相遇。所以不要相遇了再分离,综上。(HansBug:嗨。。这话写的。。。为啥感觉越读越戳泪点TT)

(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;
31 procedure add(x,y,z:longint;var a:map);inline;
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
67      readln(a1,a2,a3,n,m);
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
72               readln(j,k);
73               add(j,k,1,a);
74               add(k,j,1,a);
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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术之路

WPF MVVM实现TreeView

今天有点时间,做个小例子WPF MVVM 实现TreeView 只是一个思路大家可以自由扩展 文章最后给出了源码下载地址 图1 ?    图2     ? 模...

382100
来自专栏逍遥剑客的游戏开发

WOW小地图生成

34730
来自专栏非典型技术宅

iOS实践:一步步实现星级评分1. 创建星星2. 优化3. 灵异事件

20940
来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

31150
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 aggregate和treeAggregate从原理到应用

由于treeAggregate是在aggregate基础上的优化版本,因此先来看看aggregate是什么.

17400
来自专栏码匠的流水账

聊聊storm client的netty buffer watermark

本文主要研究一下storm client的netty buffer watermark

12020
来自专栏逆向与安全

菜鸟 学注册机编写之 “RSA”

选取两个别人不知道的大素数p, q. 公共模n = p*q 欧拉值φ(n) = (p-1)(q-1) 选取公匙(加密匙) e , 条件是1< e <φ(n...

22100
来自专栏技术随笔

医学影像中Dicom的常用Tag分类与说明

55170
来自专栏一个会写诗的程序员的博客

Spring Data JPA WITH Kotlin

异常消息: No default constructor for entity: : com.ak47.cms.cms.entity.StockIndex; n...

9620
来自专栏jeremy的技术点滴

python开发小技巧

34840

扫码关注云+社区

领取腾讯云代金券