poj 2662 A Walk Through the Forest

发布时间:2016-12-10 22:55:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 2662 A Walk Through the Forest",主要涉及到poj 2662 A Walk Through the Forest方面的内容,对于poj 2662 A Walk Through the Forest感兴趣的同学可以参考一下。

题目意思,可以从A走到B当且仅当B到终点的最短路径小于A到终点的最短路径 问一共存在几条这样的路径 我用dijkstra各做了一遍,呵呵 个中细节还需细细体味啊 View Code #include<stdio.h>#include<queue>#include<string.h>using namespace std;const int INF = 9999999;struct NODE{ int v,w; int next;}list[10000000];int tot;int head[1010];int dis[1010];int vis[1010];int sum[1010];queue<int> Q;int n,m;void init(){ int i; for(i=0;i<=1000000;i++) list[i].w=INF; memset(head,-1,sizeof(head));}void add(int s,int t,int w){ list[tot].v=t; list[tot].w=w; list[tot].next=head[s]; head[s]=tot++;}void spfa(int src){ int i,j,u; while(!Q.empty()) Q.pop(); memset(vis,0,sizeof(vis)); for(i=0;i<=1000;i++) dis[i]=INF; Q.push(src); vis[src]=1; dis[src]=0; while(!Q.empty()) { u=Q.front(); Q.pop(); vis[u]=0; for(j=head[u];j!=-1;j=list[j].next) { int e=list[j].v; if(dis[e]>list[j].w+dis[u]) { dis[e]=list[j].w+dis[u]; if(!vis[e]) { Q.push(e); vis[e]=1; } } } }}int dfs(int i){ int j; if(i==2) return 1; if(sum[i]!=-1) return sum[i];//很重要,避免重复搜索,否则超时。 int cnt=0;// printf("i disi=%d %d\n",i,dis[i]); for(j=head[i];j!=-1;j=list[j].next) { if(dis[i]>dis[list[j].v]&&list[j].w<INF) { //printf("i=%d to=%d\n",i,list[j].v);//这里输出后,dfs的调用过程就一清二楚了 cnt+=dfs(list[j].v); // printf("cnt=%d\n",cnt); } } sum[i]=cnt;//printf("sum[%d]=%d\n",i,sum[i]); return sum[i];}int main(){ int a,b,d; while(scanf("%d",&n),n) { scanf("%d",&m); init(); while(m--) { scanf("%d%d%d",&a,&b,&d); add(a,b,d); add(b,a,d); } spfa(2); memset(sum,-1,sizeof(sum)); int ans=dfs(1); printf("%d\n",ans); } return 0;}/*5 61 3 21 4 23 4 31 5 124 2 345 2 24sum[5]=1sum[4]=1sum[1]=227 81 3 11 4 13 7 17 4 17 5 16 7 15 2 16 2 1sum[6]=1sum[5]=1sum[7]=2sum[4]=2sum[3]=2sum[1]=44*/

上一篇:一个人的旅行
下一篇:字典树 + DP

相关文章

相关评论