Sightseeing trip
题目描述：
在Adelton城有一个桑给巴尔岛的旅行社。它已决定提供它的客户，其中一些景点，观光小镇。为了赚取尽可能多的钱，该机构接受了一个精明的决定：有必要找到最短的路线，开始和结束在同一个地方。你的任务是写一个程序，找到这样的路线。
镇上有n个景点，编号从1到N和M个双向道路编号从1到M。
两个景点可以通过多条道路连接，但没有道路连接本身景点。每一条观光路线是一个有序的道路编号，道路数k大于2。观光路线是无重复景点的环路。观光路线的长度是所有路线长度之和。您的程序必须找到长度最小的观光路线，或指定它是不可能的。
样例输入
4 6 //4个景点6条路
1 2 40 //双向路，长度。
1 3 50
1 40 60 //这个应该是出错了，不过不影响结果
2 3 10
2 4 30
3 4 20
样例输出：
2 3 4
思路：
这是到最小环+路径的问题，首先想到的是floyd算法，通过d[i][j] + map[i][k] + map[k][j] < mi求最小环，没找到就输出“No solution.”，每次更新最小环，都更新下路径数组ans[]，用一个函数寻找i与j之间经过的点。用path[i][j]表示i到j最短路径上j前面的一个点。
代码：
#include <cstdio>
#include <cstring>
int const MAX = 105;
int const INF = 0xfffffff;
int d[MAX][MAX], map[MAX][MAX], path[MAX][MAX];//d是最小路径长度，map是记录路径，path是最小路径经过的点
int n, m, ans[MAX], mi, cnt;
void init()//初始化数据
{for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){d[i][j] = INF;map[i][j] = INF;path[i][j] = i;}}}void Floyd()
{mi = INF;for(int k = 1; k <= n; k++){for(int i = 1; i < k; i++){for(int j = 1; j < i; j++){if(d[i][j] + map[i][k] + map[k][j] < mi)//更新最小环{mi = d[i][j] + map[i][k] + map[k][j]; int tmp = j;cnt = 0;//重新记录路径while(tmp != i)//找i和j之间的点{ans[cnt++] = tmp;tmp = path[i][tmp];}ans[cnt++] = i;ans[cnt++] = k;}}}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(d[i][k] + d[k][j] < d[i][j]){d[i][j] = d[i][k] + d[k][j];//path[i][j]表示i到j最短路径上j前面的一个点 //所以此时i到j的最短路径上j前一个点为k到j最短路径上j的前一个点path[i][j] = path[k][j]; }}}}}int main(){int u, v, w;scanf("%d %d", &n, &m);init();for(int i = 0; i < m; i++){scanf("%d %d %d", &u, &v, &w);if(d[u][v] > w) //会有重复路出现，选择最小的路径 {d[u][v] = d[v][u] = w;map[u][v] = map[v][u] = w;}}Floyd();if(mi == INF)//环仍为初始值printf("No solution.\n");else
//输出路径{printf("%d", ans[0]);for(int i = 1; i < cnt; i++)printf(" %d", ans[i]);printf("\n");}}