题解P2910

· · 题解

这道题显而易见是一道Floyd模板题，从Floyd的基本思想我们可以发现Floyd就是DP，那么我们不仅仅可以用二维数组，还可以用三维数组解决。

Floyd的基本思想就是绕路依靠中转站取最小值，那么我们考虑前p个中转站，Map[p][i][j]表示在第k个中转站时，i到j的最短距离，那么显而易见Map[p][i][j]=min(Map[p-1][i][j],Map[p-1][i][p]+Map[p-1][p][j])

代码奉上：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10001],Map[101][101][101];
long long ans;
inline int min(const int &a,const int &b)
{
    return a<b?a:b;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;++i)
        scanf("%d",a+i);
    memset(Map,0x3f,sizeof(Map));
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=n;++j)
            scanf("%d",Map[0][i]+j);
    for(register int p=1;p<=n;++p)
        for(register int i=1;i<=n;++i)
            for(register int j=1;j<=n;++j)
                Map[p][i][j]=min(Map[p-1][i][j],Map[p-1][i][p]+Map[p-1][p][j]);
    for(register int i=2;i<=m;++i)
        ans+=Map[n][a[i-1]][a[i]];
    printf("%lld\n",ans);
    return 0;
}