本文主要是介绍URAL1004 Sightseeing Trip Floyd 最小环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
const int maxn=110;
int dist[maxn][maxn], map[maxn][maxn]; //最短距离，原图
int pre[maxn][maxn]; // pre[i,j]记录最短路里，j前面一个点
int path[maxn]; // 答案路径
int n, m, num, minc; // num记录path里有多少个点，minc是最短环长度
int main()
{
int u, v, cost;
while(cin >> n && n){
if(n<0) break;
cin >> m;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dist[i][j]=map[i][j]=INF;
pre[i][j]=i;
}
}
for(int i=1; i<=m; i++){
scanf("%d %d %d",&u,&v,&cost);
if(dist[u][v]>cost) //重边
map[u][v]=map[v][u]=dist[u][v]=dist[v][u]=cost;
}
// floyd
minc=INF;
for(int k=1; k<=n; k++){
// k还没加入(i,j)最短路，更新最短环
for(int i=1; i<k; i++){
for(int j=i+1; j<k; j++){
int ans=dist[i][j]+map[i][k]+map[k][j];
if(ans<minc){ //找到最优解
minc=ans;
num=0;
int p=j;
while(p!=i){ //逆向寻找前驱遍历的路径并将其存储起来
path[num++]=p;
p=pre[i][p];
}
path[num++]=i;
path[num++]=k;
}
}
}
//用k更新i到j的最短路径
for(int i=1; i<=n; i++){
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];
pre[i][j]=pre[k][j];
}
}
}
}// end Floyd
if(minc==INF) puts("No solution.");
else{
printf("%d",path[0]);
for(int i=1; i<num; i++)
printf(" %d",path[i]);
puts("");
}
}
return 0;
}这篇关于URAL1004 Sightseeing Trip Floyd 最小环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
