POJ 1734 拓展Floyd

//搜索比较好想  
#include <cstdio>  
#include <cstring>  
#include <iostream>  
#define find_min(a,b) a<b?a:b  
#define N 150  
#define inf 0x7ffffff  
using namespace std;  
inline int Min(int a,int b){return 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<k;i++)  
                for(j=i+1;j<k;j++)  
                {  
                    int len=dis[i][j]+map[i][k]+map[k][j];  
                    if(len<ans){  
                        ans=len;  
                        num=0;  
                        int now=j;  
                        while(now!=i)  
                            path[num++]=now,now=pre[i][now];  //pre[i][j] 表示 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<num-1;i++)printf("%d ",path[i]);  
        printf("%d\n",path[i]);  
    }  
    return 0;  
}