Flody算法求解多源最短路问题
蓝桥公园
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=409;
int n,m,q,d[N][N];
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
memset(d,0x3f,sizeof(d));//初始化d极大值
for(int i=1;i<=n;i++)d[i][i]=0;//自己到自己距离为0
while(m--){
int u,v,w;cin>>u>>v>>w;
d[u][v]=min(d[u][v],w);//双向图,可能有重边,取小
d[v][u]=min(d[v][u],w);
}
for(int k=1;k<=n;k++)//Flody
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
while(q--){//q次询问
int st,ed;cin>>st>>ed;
if(d[st][ed]>=0x3f3f3f3f3f3f3f3f)cout<<"-1"<<'\n';//2e18也可
else cout<<d[st][ed]<<'\n';
}
}
小蓝组网
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
int n,m,d[N][N];
bool ok=1;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
memset(d,0x3f,sizeof(d));
for(int i=1;i<=n;i++)d[i][i]=0;
while(m--){
int a,b;cin>>a>>b;
d[a][b]=min(d[a][b],1LL);
d[b][a]=min(d[b][a],1LL);
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(d[i][j]>=0x3f3f3f3f3f3f3f3f){
ok=0;
continue;
}
ans=max(ans,d[i][j]);
}
if(!ok)cout<<"NO"<<'\n';
else cout<<"YES"<<'\n';
cout<<ans;
}
最短路问题
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n,q,g[N][N];
bool is_prime(int x){
if(x<2)return 0;
for (int i = 2; i*i <= x ; i ++ )
if (x % i == 0)
return 0;
return 1;
}
void floyd(){
for (int k = 1; k <= n; ++ k )
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main(){
cin >> n >> q;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; ++ i )
for (int j = i + 1; j <= n; ++ j )
if (is_prime(i) + is_prime(j) == 1)
g[i][j] = i*j/__gcd(i,j);
floyd();
while (q -- ){
int a, b;cin >> a >> b;
if (g[a][b] == 0x3f3f3f3f3f3f)cout<<"-1"<<'\n';
else
cout << g[a][b] <<'\n';
}
}
会面
#include <bits/stdc++.h>
using namespace std;
const int N = 209;
int n,m,g[N][N];
int s1,e1,s2,e2;
void floyd(){
for (int k = 1; k <= n; ++ k )
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; ++ i )g[i][i] = 0;
while (m -- ){
int a, b, c;cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[b][a],c);
}
cin >> s1 >> e1 >> s2 >> e2;
floyd();
int res=0x3f3f3f3f3f;
for (int k = 1; k <= n; ++ k )
res=min(res,max(g[s1][k],g[s2][k])+max(g[k][e1],g[k][e2]));
cout<<(res >= 0x3f3f3f3f3f? -1: res) << '\n';
}