# 【BZOJ1624】[Usaco2008 Open]Clear And Present Danger 寻宝之路

## 样例输入 SampleInput

10 10
1
7
2
5
6
5
6
2
7
10
0 72 24 67 81 10 91 83 94 32
85 0 70 68 79 11 12 3 10 63
33 3 0 4 96 36 90 3 57 42
66 82 22 0 15 54 45 83 65 42
69 10 34 5 0 59 27 34 55 61
80 81 85 59 35 0 77 45 89 26
17 78 25 35 68 48 0 2 12 6
70 28 79 93 14 7 76 0 79 64
63 28 0 81 64 80 1 45 0 66
81 85 11 16 68 16 8 99 19 0

202

Silver

BZOJ 1624

## 代码 Code

Floyd 求出任意两座岛之间最小的危险指数，然后按照题目给的顺序走一遍求和。

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
int a[10005];
int f[105][105];
int i,j,t,n,m,l,r,k,z,y,x,ans;
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) for (j=1;j<=n;j++) scanf("%d",&f[i][j]);
for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++)
{
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
ans=0;
a[0]=1;
for (i=1;i<=m;i++) ans+=f[a[i-1]][a[i]];
printf("%d\n",ans);
return 0;
}``````