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
Input
Output
Sample Input
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
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
题解:乍一看这个要求的路径还得经过如下的点,然后取最短路径,吓我一跳——直到我看到了必须依次经过以下点。。。这样一来就没啥了,先是Floyd一遍弄出各个点之间的最短路径,然后既然要求必须按序经过且不一定相邻,则直接累加各个段的最短路就Accept啦*^_^*。。。(PS:Floyd时不要排除a[i,k]或者a[k,j]为零的状况,因为在这个题目中不存在不直接相连的点,就算真的出现0,代表的也是真正意义上的两点距离为零,我虽然没有因此跪过但还是觉得最好留心点。。。)
var
i,j,k,m,n:longint;
l:int64;
a:array[..,..] of int64;
b:array[..] of longint;
begin
readln(n,m);
for i:= to m do
readln(b[i]);
b[]:=;
b[m+]:=n;
for i:= to n do
begin
for j:= to n do
read(a[i,j]);
readln;
end;
for k:= to n do
for i:= to n do
begin
if (i=k) then continue;
for j:= to n do
begin
if (i=j) or (k=j) then continue;
if (a[i,k]+a[k,j])<a[i,j] then a[i,j]:=a[i,k]+a[k,j];
end;
end;
for i:= to m do
l:=l+a[b[i],b[i+]];
writeln(l);
end.
最新文章
- jQuery第二篇 (帅哥)
- IOS中无缓存的图片载入
- [PHP]Yii2框架的坑
- mysql-删除日志文件命令详解
- 【项目经验】navicat工具 SQLServer数据库迁移MySQL
- SphinxSE 一些SQL查询语句
- yii2-user
- [转载] 动态链接库dll的 静态加载 与 动态加载
- Informix SDK對比
- C++中的多态
- selenium+python find_element_by_css_selector方法使用
- [转] C#中发送消息给指定的窗口,以及接收消息
- Uva 11198 - Dancing Digits
- 关于Jquery中ajax方法data参数用法的总结
- hdu_5904_LCIS(DP)
- SSE再学习:灵活运用SIMD指令6倍提升Sobel边缘检测的速度(4000*3000的24位图像时间由180ms降低到30ms)。
- (三):C++分布式实时应用框架——系统管理模块
- Jmeter分布式部署测试-----远程连接多台电脑做压力性能测试
- Android/IOS手机使用Fiddler抓包
- [SoapUI] 通过JSONAssert比较两个环境的JSON Response,定制化错误信息到Excel