[USACO08OPEN]寻宝之路Clear And Present Danger

题目描述

Farmer John is on a boat seeking fabled treasure on one of the N (1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean Sea.

The treasure map tells him that he must travel through a certain sequence A_1, A_2, ..., A_M of M (2 <= M <= 10,000) islands, starting on island 1 and ending on island N before the treasure will appear to him. He can visit these and other islands out of order and even more than once, but his trip must include the A_i sequence in the order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <= danger <= 100,000) between each pair of islands. The total danger rating of his mission is the sum of the danger ratings of all the paths he traverses.

Help Farmer John find the least dangerous route to the treasure that satisfies the treasure map's requirement.

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

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

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

输入格式：

第一行：两个用空格隔开的正整数N和M

第二到第M+1行：第i+1行用一个整数Ai表示FJ必须经过的第i个岛屿

第M+2到第N+M+1行：第i+M+1行包含N个用空格隔开的非负整数分别表示i号小岛到第1...N号小岛的航线各自的危险指数。保证第i个数是0。

输出格式：

第一行：FJ在找到宝藏的前提下经过的航线的危险指数之和的最小值。

输入样例

输出样例

看了一眼想用spfa写但是看了看可怜的数据范围n<=100 用Floyd写似乎更容易点
扔代码 ``` //#define fre yes

include

using namespace std;

const int maxn = 20005;
int d[105][105];

int f[maxn];

int n,m,ans;

templateinline void read(T&x)
{
x = 0;char c;int lenp = 1;
do { c = getchar();if(c == '-') lenp = -1; } while(!isdigit(c));
do { x = x * 10 + c - '0';c = getchar(); } while(isdigit(c));
x *= lenp;
}

int main()
{
read(n);read(m);
for (int i=1;i<=m;i++)
{
int x;
read(x);
f[i] = x;
}

for (int i=1;i<=n;i++)
{
    for (int j=1;j<=n;j++)
    {
        int x;
        read(x);
        d[i][j] = x;
    }
}

for (int k=1;k<=n;k++)
{
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
        } }
} 

for (int i=1;i<m;i++) ans += d[f[i]][f[i+1]];

printf("%d\n",ans);
return 0;

}