题解 P2910 【[USACO08OPEN]寻宝之路Clear And Present Danger】

hyoi_ctime · 2017-10-10 15:01:37 · 题解

首先可以看出这是一个有向图（我是这么认为的），这个题的输入把每一个危险值都给了，所以就不需要初始化f数组了；跑一遍floyd；求出各个岛屿之间的最小危险值，然后就根据题目所要求的路径按照最小危险值走。

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=100+5;
int n,m;
int a[10001],f[100][100];
inline void read()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)scanf("%d",&f[i][j]);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
    int ans=0,t=1;
    for(int i=1;i<=m;i++)
    {
        ans+=f[t][a[i]];
        t=a[i];//t为当前所处位置，每走一次就更新一次。
    }
    printf("%d",ans);
}
int main()
{
    read();
    return 0; 
}