描述 Description
农夫约翰正驾驶一条小艇在牛勒比海上航行．
海上有 N(1≤N≤100) 个岛屿，用 1 到 N 编号．约翰从 1 号小岛出发，最后到达 N 号小岛．一张藏宝图上说，如果他的路程上经过的小岛依次出现了 Ai，A2，…，AM(2≤M≤10000) 这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 Dij(0≤Dij≤100000) 来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？
输入格式 InputFormat
第 1 行输入 N 和 M，之后 M 行一行一个整数表示 A 序列，之后输入一个 NxN 的方阵，表示两两岛屿之间航线的危险指数．数据保证 Dij=Dji，Dii=0．
输出格式 OutputFormat
最小的危险指数和．
样例输入 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
样例输出 SampleOutput
202
来源 Source
Silver
代码 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;
}