首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。