AcWing 344. 观光之旅
原题链接
中等
作者:
追着你行走
,
2021-01-05 12:14:49
,
所有人可见
,
阅读 417
spfa无向图最小环问题
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,inf=0x3f3f3f3f;
typedef long long ll;
#define max(a,b) (a>=b?a:b)
#define min(a,b) (a>=b?b:a)
int n,m,dist[220][220],ar[220][220],pos[220][220];
int ans=inf;
vector<int> path;
void updpath(int x,int y){
if(pos[x][y]==0) return ;
updpath(x,pos[x][y]);
path.push_back(pos[x][y]);
updpath(pos[x][y],y);
return ;
}
void spfa(){
for(int k=1;k<=n;k++){
for(int i=1;i<k;i++){ //dynamic planning
for(int j=i+1;j<k;j++){
if( (ll) dist[i][j]+ar[j][k]+ar[k][i]<ans){
ans=dist[i][j]+ar[j][k]+ar[k][i] ;
//todo record the path
path.clear();
path.push_back(i);
updpath(i,j);
path.push_back(j);
path.push_back(k);
}
}
}
for(int i=1;i<=n;i++){ //spfa
for(int j=1;j<=n;j++){
if(dist[i][j]>dist[i][k]+dist[k][j]){
dist[i][j]=dist[i][k]+dist[k][j];
pos[i][j]=k; //record path position
}
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n>>m;
memset(dist,0x3f,sizeof(dist)); //ans=dist[0][0];
for(int i=1;i<=n;i++) dist[i][i]=0;
while(m--){
int u,v,l;
cin>>u>>v>>l;
dist[u][v]=dist[v][u]=min(dist[u][v],l) ;
}
memcpy(ar,dist,sizeof(dist));
spfa();
//print
//todo
if(ans==inf) cout<<"No solution.\n";
else {
for(auto it:path)
cout<<it<<' ';
}
return 0;
}