1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 377  Solved: 269

[Submit][Status]

Description

    农夫约翰正驾驶一条小艇在牛勒比海上航行.

    海上有N(1≤N≤100)个岛屿,用1到N编号.约翰从1号小岛出发,最后到达N号小岛.一

张藏宝图上说,如果他的路程上经过的小岛依次出现了Ai,A2,…,AM(2≤M≤10000)这样的序列(不一定相邻),那他最终就能找到古老的宝藏.  但是,由于牛勒比海有海盗出没.约翰知道任意两个岛屿之间的航线上海盗出没的概率,他用一个危险指数Dij(0≤Dij≤100000)来描述.他希望他的寻宝活动经过的航线危险指数之和最小.那么,在找到宝藏的前提下,这个最小的危险指数是多少呢?

Input

    第1行输入N和M,之后M行一行一个整数表示A序列,之后输入一个NxN的方阵,表示两两岛屿之间航线的危险指数.数据保证Dij=Dji,Dii=0.

Output

    最小的危险指数和.

Sample Input

3 4 1 2 1 3 0 5 1 5 0 2 1 2 0 INPUT DETAILS: There are 3 islands and the treasure map requires Farmer John to visit a sequence of 4 islands in order: island 1, island 2, island 1 again, and finally island 3. The danger ratings of the paths are given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have danger ratings of 5, 2, and 1, respectively.

Sample Output

7 OUTPUT DETAILS: He can get the treasure with a total danger of 7 by traveling in the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement (1, 2, 1, and 3) is satisfied by this route. We avoid the path between islands 1 and 2 because it has a large danger rating.

HINT

Source

Silver

 题解:乍一看这个要求的路径还得经过如下的点,然后取最短路径,吓我一跳——直到我看到了必须依次经过以下点。。。这样一来就没啥了,先是Floyd一遍弄出各个点之间的最短路径,然后既然要求必须按序经过且不一定相邻,则直接累加各个段的最短路就Accept啦*^_^*。。。(PS:Floyd时不要排除a[i,k]或者a[k,j]为零的状况,因为在这个题目中不存在不直接相连的点,就算真的出现0,代表的也是真正意义上的两点距离为零,我虽然没有因此跪过但还是觉得最好留心点。。。)

 1 var
 2    i,j,k,m,n:longint;
 3    l:int64;
 4    a:array[0..200,0..200] of int64;
 5    b:array[0..20000] of longint;
 6 begin
 7      readln(n,m);
 8      for i:=1 to m do
 9          readln(b[i]);
10      b[0]:=1;
11      b[m+1]:=n;
12      for i:=1 to n do
13          begin
14               for j:=1 to n do
15                   read(a[i,j]);
16               readln;
17          end;
18      for k:=1 to n do
19          for i:=1 to n do
20              begin
21                   if (i=k) then continue;
22                   for j:=1 to n do
23                       begin
24                            if (i=j) or (k=j) then continue;
25                            if (a[i,k]+a[k,j])<a[i,j] then a[i,j]:=a[i,k]+a[k,j];
26                       end;
27              end;
28      for i:=0 to m do
29          l:=l+a[b[i],b[i+1]];
30      writeln(l);
31 end.
32                    

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

HDU6370:Werewolf 推理+拓扑排序 2018第六场杭电多校

"The Werewolves" is a popular card game among young people.In the basic game, th...

682
来自专栏HansBug's Lab

1708: [Usaco2007 Oct]Money奶牛的硬币

1708: [Usaco2007 Oct]Money奶牛的硬币 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 5...

2627
来自专栏数据结构与算法

1010. 邮寄包裹

1010. 邮寄包裹 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 某邮局对邮寄包裹有如下...

40211
来自专栏玄魂工作室

56行Python代码实现身份证字典生成器

最近过生日,女朋友送了几本Python黑客编程的书(没错,小黑阔也是可以有女朋友的)。哈哈,皮一下就是很开心。

2143
来自专栏数据结构与算法

2017.5.26暴力赛解题报告

预计分数:T1:40AC+60TLE      T2:40AC+60TLE        T3:10AC+90TLE      总分=90 实际分数:T1:10...

3836
来自专栏HansBug's Lab

2016: [Usaco2010]Chocolate Eating

2016: [Usaco2010]Chocolate Eating Time Limit: 10 Sec  Memory Limit: 162 MB Subm...

3375
来自专栏C语言及其他语言

【每日一题】问题 1146: 舍罕王的失算

关注我们 题目描述 相传国际象棋是古印度舍罕王的宰相达依尔发明的.舍罕王十分喜爱象棋,决定让宰相自己选择何种赏赐.这位聪明的宰相指着8*8共64格的象棋说:陛...

33011
来自专栏ml

HDUOJ-----4506小明系列故事——师兄帮帮忙

小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3276...

2857
来自专栏Java帮帮-微信公众号-技术文章全总结

【学习经验】Java中常用英文

【学习经验】Java中常用英文 第一章: public['pʌblik] 公共的,公用的 static['stætik] 静的;静态的...

36010
来自专栏HansBug's Lab

1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2787

扫码关注云+社区