Sightseeing trip POJ - 1734 -Floyd 最小环

POJ - 1734

思路 : Floyd 实质 dp ,优化掉了第三维. dp [ i ] [ j ] [ k ] 指的是前k个点优化后    i  ->  j   的最短路。

所以我们就可以利用这个性质去求 最小环，最小环的构成可以看作是由一条  i -> k    k->j   加上 dp [ i ] [ j ]的最短路

那么我们可以利用  还没有用 k 优化的  i - >j 的最短路 去求，这样保证了 ，这是一个真正的环。

#include<stdio.h>

#include<iostream>

using namespace std;

#define maxn 123

#define inf 1e8

int dis[maxn][maxn],n,key;

int gra[maxn][maxn],m,id;

int u,v,w,pre[maxn][maxn],ans[maxn];

void floyd()

{

    key=inf;

    for(int k=1; k<=n; k++)

    {

        for(int i=1; i<k; i++)

        {

            for(int j=i+1; j<k; j++)

            {

                int tmp=dis[i][j]+gra[i][k]+gra[k][j];

                if(tmp<key)

                {

                    key=tmp;

                    id=0;

                    int p=j;

                    while(p!=i)

                    {

                        ans[id++]=p;

                        p=pre[i][p];

                    }

                    ans[id++]=i;

                    ans[id++]=k;

                }

            }

        }

        for(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];

                    pre[i][j]=pre[k][j];

                }

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        key=inf;

        for(int i=1; i<=n; i++)

            for(int j=1; j<=n; j++)

            {

                gra[i][j]=dis[i][j]=inf;

                pre[i][j]=i;

            }

        for(int i=0; i<m; i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            gra[u][v]=gra[v][u]=dis[u][v]=dis[v][u]=min(gra[u][v],w);

        }

        floyd();

        if(key==inf)printf("No solution.\n");

        else

        {

            printf("%d",ans[0]);

            for(int i=1; i<id; i++)

                printf(" %d",ans[i]);

            printf("\n");

        }

    }

    return 0;

}