学步园

这道题目是floyd的经典，floyd的核心思想就是动态规划从k=0->n来松弛i->j的路径，

这样我们可以这样思考这个环，里面肯定有最大的下标，设为k，与之相邻的是i和j,然后i->j的最短路肯定在用k松弛前已经更新完，换句话说就是

我们floyd时候先找环再松弛，因为floyd的外层到k时，i->j的最短路上肯定没有k所以这个环不会存在相同的点，代码如下:

#include<iostream>
#include<cstring>
#include<memory>
#include<cstdio>
#include<algorithm>
using namespace std;
int g[110][110],gg[110][110],cen[110][110];
int path[110],cnt;
const int inf=99999999;
int n,m;
void init()
{
	memset(cen,-1,sizeof(cen));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			g[i][j]=gg[i][j]=inf;
			g[i][i]=gg[i][i]=0;
	}
}
void gao(int i,int j)
{
	int m=cen[i][j];
	if(m==-1)
	{
		path[cnt++]=j;
		return;
	}
	gao(i,m);
	gao(m,j);
	return;
}
int main()
{
	while(2==scanf("%d%d",&n,&m))
	{
		init();
		int a,b,c;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			a--;
			b--;
			if(c<g[a][b])
				g[a][b]=g[b][a]=gg[a][b]=gg[b][a]=c;
		}
		int ans=inf;
		for(int k=0;k<n;k++)
		{
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
				{
					if(i==k||i==j||k==j)continue;
					if(gg[i][j]+g[i][k]+g[j][k]<ans)
					{
						ans=gg[i][j]+g[i][k]+g[j][k];
						cnt=0;
						path[cnt++]=i;
						gao(i,j);
						path[cnt++]=k;
					}
				}
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
				{
					if(i==k||i==j||k==j)continue;
					if(gg[i][k]+gg[k][j]<gg[i][j])
					{
						gg[i][j]=gg[i][k]+gg[k][j];
						cen[i][j]=k;
					}
				}
		}
		if(ans==inf)
		{
			printf("No solution.\n");
			continue;
		}
		for(int i=0;i<cnt;i++)
		printf("%d%c",path[i]+1,i==cnt-1?'\n':' ');
	}
	return 0;
}