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是中转点
//也就是把每个点都作为中转点枚举一次
可以看下面两道题,可以加深对这个算法的理解
#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;
}
//直接用一个东西来记录一下最后一次中专的点不久可以了吗
#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;
}
标签:int,中转,cin,wi,算法,Floyd,关键点
From: https://www.cnblogs.com/basicecho/p/16882014.html