首页 > 代码库 > POJ 1734 Sightseeing trip

POJ 1734 Sightseeing trip

题目大意:

求一个最小环。

用Floyd 求最小环算法。

#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <cmath>#include <cstring>using namespace std;#define INF 0xfffffff#define maxn 260int G[maxn][maxn], dist[maxn][maxn];int Pre[maxn][maxn], Path[maxn];int m, n, CrossNum = 0;void SearchPath(int Star,int End){    while(Star != End)    {        Path[CrossNum ++] = Star;        Star = Pre[Star][End];    }    Path[CrossNum ++] = Star;}void Floyd(){    int MinLoop = INF;    for(int k=1; k<=n; k++)    {        for(int i=1; i<k; i++)        {            for(int j=i+1; j<k; j++)            {                if( dist[i][j] + G[i][k] + G[k][j] < MinLoop )                {                    MinLoop =  dist[i][j] + G[i][k] + G[k][j];                    CrossNum = 0;                    SearchPath(i,j);                    Path[CrossNum++] = k;                }            }        }        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)            {                if(dist[i][j] > dist[i][k] + dist[k][j])                {                    dist[i][j] = dist[i][k] + dist[k][j];                    Pre[i][j] = Pre[i][k];                }            }        }    }}void Init(){    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)        {            dist[i][j] = G[i][j] = INF;            Pre[i][j] = j;            CrossNum = 0;        }    }}int main(){    while(cin >> n >> m)    {        Init();        for(int i=0; i<m; i++)        {            int a, b, c;            cin >> a >> b >> c;            G[a][b] = G[b][a] = dist[a][b] = dist[b][a] = min(dist[a][b], c);        }        Floyd();        if( CrossNum)        {            for(int i=0; i<CrossNum - 1; i++)            {                printf("%d ", Path[i]);            }            printf("%d\n", Path[CrossNum - 1]);        }        else            cout <<"No solution." << endl;    }    return 0;}

 

POJ 1734 Sightseeing trip