题目：
gbn最近打算穿过一个森林，但是他比较傲娇，于是他决定只走一些特殊的道路，他打算只沿着满足如下条件的（A,B）道路走：存在一条从B出发回家的路，比所有从A出发回家的路径都短。你的任务是计算一共有多少条不同的回家路径。其中起点的编号为1，终点的编号为2.
分析：
先求出每个点到终点的距离，根据题目要求找d[u]>d[v]的路径(u,v)走，计算路径数即可。
代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 #define Maxn 1010 9 10 struct node 11 { 12 int x,y,c,next; 13 }t[2*Maxn*Maxn];int len; 14 15 int n,m; 16 int first[Maxn],dis[Maxn],f[Maxn]; 17 bool inq[Maxn]; 18 19 void ins(int x,int y,int c) 20 { 21 t[++len].x=x;t[len].y=y;t[len].c=c; 22 t[len].next=first[x];first[x]=len; 23 } 24 25 void spfa(int s) 26 { 27 queue<int > q; 28 while(!q.empty()) q.pop(); 29 q.push(s); 30 memset(dis,63,sizeof(dis)); 31 memset(inq,0,sizeof(inq)); 32 dis[s]=0; 33 while(!q.empty()) 34 { 35 int x=q.front();q.pop(); 36 for(int i=first[x];i;i=t[i].next) 37 { 38 int y=t[i].y; 39 if(dis[y]>dis[x]+t[i].c) 40 { 41 dis[y]=dis[x]+t[i].c; 42 if(!inq[y]) {inq[y]=1;q.push(y);} 43 } 44 } 45 inq[x]=0; 46 } 47 } 48 49 int ffind(int x) 50 { 51 if(f[x]!=-1) return f[x]; 52 f[x]=0; 53 for(int i=first[x];i;i=t[i].next) if(dis[x]>dis[t[i].y]) 54 { 55 f[x]+=ffind(t[i].y); 56 } 57 return f[x]; 58 } 59 60 int main() 61 { 62 while(1) 63 { 64 scanf("%d",&n); 65 if(n==0) break; 66 scanf("%d",&m); 67 len=0; 68 memset(first,0,sizeof(first)); 69 for(int i=1;i<=m;i++) 70 { 71 int x,y,c; 72 scanf("%d%d%d",&x,&y,&c); 73 ins(x,y,c);ins(y,x,c); 74 } 75 spfa(2); 76 memset(f,-1,sizeof(f)); 77 f[2]=1; 78 ffind(1); 79 printf("%d ",f[1]); 80 } 81 return 0; 82 }
2016-03-21 13:49:15