# 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号小岛．一

## Input

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

最小的危险指数和．

## 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.

## 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
8      for i:=1 to m do
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
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 条评论

## 相关文章

### 1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1245  Solv...

3296

### string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考，string函数库当然是首选，除此之外，像qsort，S...

2017

842

2075

### 1010. 邮寄包裹

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

41811

3624

781

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

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

722

3447

### 2016: [Usaco2010]Chocolate Eating

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

3435