J – 坑爹的叶萝卜Description
叶萝卜喜欢旅游，好了大家应该知道这是个什么题了。
话说萝卜旅游喜欢节省体力。太远的路他可不想走~ 所以萝卜想让你帮他设计个
程序解决他的偷懒问题。
萝卜也是个有名的acmer，所以他可不想就这么简单让你AC 了，所以呢，萝卜
想问，从S 点到达E点的最短路径的条数有多少条？
Input
第一行为T，代表有T组测试数据。
每组测试数据的第一行有两个参数V,E。分别代表景点的个数和两个景点之间的
小路条数。(V<=10000,E<=10000)
稍后E 行包含三个参数,a,b,c，分别表示景点a 到景点b 有一条长度为c 的小路。
每组测试数据的最后一行为起点景点S，和终点景点E。
Output
每组测试数据输出一行。(输出为一个整型<10^9)
Sample Input
1
3 4
1 2 1
2 1 1
1 3 2
2 3 1
1 3
Sample Output
2
Source
Tips@USC: bySen 2011/10/27
哈哈我出的题 很水啊~~ 不过没有人做啊！！ 坑爹不！！
#include<iostream>
#define MAXV 100005
#define MAXE 100005
using namespace std;struct Node
{int v,w;Node *next;
}edge[MAXE],*ptr[MAXV];void addEdge( int u,int v,int w,int i )
{Node *p=&edge[i];p->v=v;p->w=w;p->next=ptr[u];ptr[u]=p;
}int S,F,E,V;
int dis[MAXV],cnt[MAXV];
bool vis[MAXV];int Dijstra( )
{memset( dis,0x7F,sizeof(dis) );memset( vis,0,sizeof(vis) );memset( cnt,0,sizeof(cnt) );dis[S]=0;cnt[S]=1;int i,j,k;for( i=1;i<=V;i++ ){int min=0x7F7F7F7F;k=-1;for( j=1;j<=V;j++ )if( min>dis[j] && !vis[j] )min=dis[j],k=j;if( k==-1 )break;vis[k]=true;Node *p=ptr[k];while( p ){if( dis[p->v]>dis[k]+p->w ){cnt[p->v]=cnt[k];dis[p->v]=dis[k]+p->w;}else if( dis[p->v]==dis[k]+p->w )cnt[p->v]+=cnt[k];p=p->next;}}return cnt[F];
}int main()
{int T;//freopen( "in.txt","r",stdin );//freopen( "out.txt","w",stdout );scanf( "%d",&T ); while( T-- ){scanf( "%d %d",&V,&E );int i;for( i=0;i<=V;i++ )ptr[i]=NULL;int u,v,w;for( i=0;i<E;i++ ){scanf( "%d %d %d",&u,&v,&w );addEdge( u,v,w,i );}scanf( "%d %d",&S,&F );printf( "%d\n",Dijstra() );}return 0;
}