九野的博客，转载请注明出处：

题意：

n个点 m条无向边

下面m条有权无向边

问图中最小环的路径

学习的拓展Floyd，先找环后松弛

dfs会做的简单一点

 

//搜索比较好想#include 
    
     #include 
     
      #include 
      
       #define find_min(a,b) a
       
        b?b:a;}int map[N][N],dis[N][N],pre[N][N],path[N],n;int main(){	int i,j,k,m,u,v,d;	int num;	while(~scanf("%d%d",&n,&m))	{		for(i=1;i<=n;i++)			for(j=1;j<=n;j++)					map[i][j]=inf,  pre[i][j]=i;					while(m--)		{			scanf("%d %d %d",&u,&v,&d);			map[u][v]=map[v][u]=Min(map[v][u],d);		}		memcpy(dis,map,sizeof(map));		int ans=inf;		for(k=1;k<=n;k++)		{			for(i=1;i
        
         pre[i][j]->j						path[num++]=i;	path[num++]=k;											}				}				for(i=1;i<=n;i++)//普通的松弛k点					for(j=1;j<=n;j++)						if(dis[i][j]>dis[i][k]+dis[k][j])						{							dis[i][j]=dis[i][k]+dis[k][j];							pre[i][j]=pre[k][j];//这个学习了						}		}		if(ans==inf){printf("No solution.\n");continue;}		for(i=0;i