本文主要是介绍URAL1004 Sightseeing Trip(Folyd求最小环，打印路径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
1004. Sightseeing Trip
Time limit: 0.5 second
Memory limit: 64 MB
Memory limit: 64 MB
There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place.
Your task is to write a program which finds such a route. In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y 1, …, yk, k > 2. The road yi (1 ≤ i ≤ k − 1) connects crossing points xi and x i+1, the road yk connects crossing points xk and x 1. All the numbers x 1, …, xk should be different. The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L( y 1) + L( y 2) + … + L( yk) where L( yi) is the length of the road yi (1 ≤ i≤ k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible, because there is no sightseeing route in the town.
Input
Input contains T tests (1 ≤ T ≤ 5). The first line of each test contains two integers: the number of crossing points N and the number of roads M (3 ≤ N ≤ 100; 3 ≤ M ≤ N · ( N − 1)). Each of the next M lines describes one road. It contains 3 integers: the number of its first crossing point a, the number of the second one b, and the length of the road l (1 ≤ a, b ≤ N; a ≠ b; 1 ≤ l ≤ 300 ). Input is ended with a “−1” line.
Output
Each line of output is an answer. It contains either a string “No solution.” in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x 1 to xk from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.
Sample
| input | output |
|---|---|
5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20 4 3 1 2 10 1 3 20 1 4 30 -1 | 1 3 5 2 No solution. |
Problem Source: Central European Olympiad in Informatics 1999
题意给了一张无向图，求的是这个图的最小环（就是从某个点出发再走回它自己的最短路），并且把路径打印出来。
所以我们求出一个最短路+次短路的和就是所求的路径.我们以环权值最小为标准（最短路权值+次短路权值），记录从i~j的路径以及能松弛i和j点的k中代价最小的那个,一直更新路径，如果遇见更短的路径那么就放弃之前记录的重新记录.floyd是按照结点的顺序更新最短路的，所以我们在更新最短路之前先找到一个连接点k，当前的点k肯定不存在于已存在的最短路dis[i][j]的路径上，因为我们还没用这个k去更新最短路，这样一个环就找到了
map[]来存储原图
dis[]来存储松弛后的图
path[]记录路径
vis[][]标记两个点之间经过哪个点中转过
ans来存储当前最小的环的值，如果遇到更小的，那么就重新记录路径
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define N 110
#define inf 9999999
#define ll long long
using namespace std;
int n,m,ans,cnt;
int map[N][N],dis[N][N];
int vis[N][N],path[N];
void init()
{for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){dis[i][j]=inf;vis[i][j]=0;}
}
void record(int i,int j)//递归记录路径
{if(vis[i][j]){record(i,vis[i][j]);record(vis[i][j],j);}elsepath[cnt++]=j;
}
void floyd()
{ans=inf;for(int k=1; k<=n; k++){//找出最小环并且记录路径for(int i=1; i<k; i++)for(int j=i+1; j<k; j++)if(ans>dis[i][j]+map[i][k]+map[k][j])//如果最短路加上次短路权值可以成环，就记录{ans=dis[i][j]+map[i][k]+map[k][j];cnt=0;path[cnt++]=i;record(i,j);//回溯记录路径path[cnt++]=k;}//正常的folydfor(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(dis[i][j]>dis[i][k]+dis[k][j]){dis[i][j]=dis[i][k]+dis[k][j];vis[i][j]=k;}}
}
int main()
{int u,v,w;while(~scanf("%d",&n)&&n!=-1){scanf("%d",&m);init();for(int i=1; i<=m; i++){scanf("%d%d%d",&u,&v,&w);if(w<dis[u][v])dis[u][v]=dis[v][u]=w;}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)map[i][j]=dis[i][j];floyd();if(ans==inf)puts("No solution.");else{printf("%d",path[0]);for(int i=1; i<cnt; i++)printf(" %d",path[i]);puts("");}}return 0;
}
这篇关于URAL1004 Sightseeing Trip(Folyd求最小环，打印路径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
