Floyd算法的关键点

Floyd算法的代码很简单，就是三个for
这个算法最重要的地方就是中转点的枚举

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=max(g[i][j],g[i][k]+g[k][j]);
//其中k是中转点，i是起点，j是中转点
//也就是把每个点都作为中转点枚举一次

可以看下面两道题，可以加深对这个算法的理解

P1119 灾后重建

#include <bits/stdc++.h>
using namespace std;
const int M=205;
const int inf=0x3f3f3f3f;

int n,m;
int f[M][M];
void up(int x) {
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(f[i][j]>f[i][x]+f[x][j])
                f[i][j]=f[i][x]+f[x][j];
}
//很奇妙呀，这就是folyd的关键
//枚举中转点，也就是看那个点是可以作为中转点进行更新的
int a[M];
//每解锁一个点，就对这个点进行中转一次

int main() {
    memset(f,0x3f,sizeof(f));
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)f[i][i]=0;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        f[x][y]=f[y][x]=min(f[x][y],wi);
    }
    int now=0;
    int q;cin>>q;
    while(q--) {
        int x,y,v;
        cin>>x>>y>>v;
        while(a[now]<=v&&now<n)up(now++);
        if(a[x]>v||a[y]>v||f[x][y]==inf)cout<<"-1\n";
        else cout<<f[x][y]<<endl;
    }
    return 0;
}

P1841 [JSOI2007] 重要的城市

//直接用一个东西来记录一下最后一次中专的点不久可以了吗
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int M=205;

int g[M][M];
int n,m;
map<pii,int>mp;
bool vis[M];

void floyd() {
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) {
        if(i==j||i==k||j==k)continue;
        if(g[i][j]>g[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j],mp[{i,j}]=k;
        else if(g[i][j]==g[i][k]+g[k][j])mp[{i,j}]=0;//去掉相等的情况
    }
}
//还要去掉两个点不相通的情况

int main() {
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;i++)g[i][i]=0;
    while(m--) {
        int u,v,wi;
        cin>>u>>v>>wi;
        g[u][v]=g[v][u]=wi;
    }
    floyd();
    for(auto[x,y]:mp)vis[y]=1;
    bool flag=0;
    for(int i=1;i<=n;i++)
        if(vis[i])cout<<i<<' ',flag=1;
    if(flag==0)cout<<"No important cities.";
    return 0;
}

原文地址：http://www.cnblogs.com/basicecho/p/16882014.html