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

· · 题解

裸的\mathcal{FLOYD}......

思路：

1. 用\mathcal{FLOYD} ，就可以求出两两之间的最短距离

2. 从1到n依次累加最短路，最终输出答案即可

\mathcal{P.S.} 时间复杂度：O(n^{3})

#include<bits/stdc++.h>
using namespace std;
int n,m,dick[1010][1010],piiiii[10005];

int main()
{
    memset(dick,10000000000000,sizeof(dick));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>piiiii[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>dick[i][j];
        }
    }
    long long ans=0;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dick[i][j]=min(dick[i][j],dick[i][k]+dick[k][j]);
            }
        }
    }
    int popo=1,hop=n;
    for(int i=1;i<=m;i++)
    {
        ans+=dick[popo][piiiii[i]];
        popo=piiiii[i];
    }
    ans+=dick[popo][hop];
    cout<<ans<<endl;
    return 0;
}

\color{SpringGreen}{\text{不给个赞再走吗}}