本文主要是介绍poj 1734 Sightseeing trip(floyd 最小环),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=13143
Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.
Input
Output
Sample Input
5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20
Sample Output
1 3 5 2
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][j]>dis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j];
pre[i][j]=pre[k][j];
}
}
}
}
保证了i-->j返回时不能直接j-->i。也就满足了题目要求。输出路径问题:可以在求得小环时就把涉及到的点全部放进一个队列里,每找到一个更小的环就更新自己的队列,最后就是answer。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=105,INF=0x3f3f3f3f;
int pre[maxn][maxn],map[maxn][maxn],dis[maxn][maxn];
int res,n,m;
void init(){res=INF;memset(map,0x3f,sizeof(map));
}
int ans[maxn],top,p;
void floyd(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j]=map[i][j];pre[i][j]=i;}}for(int k=1;k<=n;k++){ for(int i=1;i<k;i++){for(int j=i+1;j<k;j++){if(dis[i][j]!=INF&&map[k][j]!=INF&&map[i][k]!=INF){int tp=dis[i][j]+map[i][k]+map[k][j];if(tp<res){top=0;res=tp;p=j;while(p!=i){ans[top++]=p;p=pre[i][p];}ans[top++]=i;ans[top++]=k;}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){dis[i][j]=dis[i][k]+dis[k][j];pre[i][j]=pre[k][j];}}}}
}
int main()
{//freopen("cin.txt","r",stdin);int a,b,c;while(cin>>n>>m){init();for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);if(map[a][b]>c)map[a][b]=map[b][a]=c;}floyd();if(res==INF) puts("No solution.");else {for(int i=0;i<top-1;i++) printf("%d ",ans[i]);printf("%d\n",ans[top-1]);}}return 0;
}
这篇关于poj 1734 Sightseeing trip(floyd 最小环)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!