【uva10917】Walk Through the Forest (最短路)

题目:

  gbn最近打算穿过一个森林,但是他比较傲娇,于是他决定只走一些特殊的道路,他打算只沿着满足如下条件的(A,B)道路走:存在一条从B出发回家的路,比所有从A出发回家的路径都短。你的任务是计算一共有多少条不同的回家路径。其中起点的编号为1,终点的编号为2.

分析:

  先求出每个点到终点的距离,根据题目要求找d[u]>d[v]的路径(u,v)走,计算路径数即可。

代码如下:

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010 struct node
{
int x,y,c,next;
}t[*Maxn*Maxn];int len; int n,m;
int first[Maxn],dis[Maxn],f[Maxn];
bool inq[Maxn]; void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
} void spfa(int s)
{
queue<int > q;
while(!q.empty()) q.pop();
q.push(s);
memset(dis,,sizeof(dis));
memset(inq,,sizeof(inq));
dis[s]=;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
if(!inq[y]) {inq[y]=;q.push(y);}
}
}
inq[x]=;
}
} int ffind(int x)
{
if(f[x]!=-) return f[x];
f[x]=;
for(int i=first[x];i;i=t[i].next) if(dis[x]>dis[t[i].y])
{
f[x]+=ffind(t[i].y);
}
return f[x];
} int main()
{
while()
{
scanf("%d",&n);
if(n==) break;
scanf("%d",&m);
len=;
memset(first,,sizeof(first));
for(int i=;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
spfa();
memset(f,-,sizeof(f));
f[]=;
ffind();
printf("%d\n",f[]);
}
return ;
}

uva 10917

2016-03-21 13:49:15

上一篇:Agile.Net 组件式开发平台 - 组件开发示例


下一篇:intent.putExtra()方法参数详解