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

· · 题解

这里是蒟蒻发的第一篇Floyed蒟蒻题解

这是一道纯Floyed题，所以一定会被Dijkstra和SPFA的大佬骂死虐得很惨

因为Floyed最短路算法连我这样的蒟蒻都能较好理解，所以是萌新必备，但时间复杂度较大O（N^3），所以不如其他方法运用广泛。

本题解法

首先利用Floyed算法计算出每两座岛之间的最小伤害（最短路），之后将相邻每两个目的地岛屿的最短路相加即是最终答案。

献上来自蒟蒻的双膝代码

#include <bits/stdc++.h>    //懒人必备 
using namespace std;
int main()
{
    long long f[101][101],a[10001],n,m,i,k,j,ans=0;
    cin>>n>>m;              //本人才学会的输入 
    for (i=1;i<=m;i++)       
    cin>>a[i];
    for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
     cin>>f[i][j];
    for (k=1;k<=n;k++)      //本人才学会的Floyed 
     for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        if (f[i][j]>f[i][k]+f[k][j]) 
         f[i][j]=f[i][k]+f[k][j]; //if以k点为中继点i到j的距离小于i到j的直线距离，则交换    
    for (i=1;i<m;i++) 
     ans+=f[a[i]][a[i+1]];  //累加相邻2个目的地的最短路径 
    cout<<ans;              //本人才学会的输出 
return 0;   
}

Floyed详见一本通 or 这里