学步园

/*
 *	poj3463 AC
 *	求最短路径以及次短路径的总数。
 *	Dijkstra+一点变化。
 *	与最短路径的Dijkstra的相比，记录的东西要增加。
 *	算法：
 *		首先，要记录到某结点的最短路径以及最短路径dis[i][2]，
 *	记录到某结点的最短路径以及次短路径是否算出的vis[i][2]，
 *	还要记录到大某结点的最短路径以及次短路径的路径数num[i][[2],
 *		
 *		tips:
 *			由于最终结果可能到达10^9量级，所以把每一条最短路径和次短路径都找出来再求和，
 *		是不可行的。这也是最开始使用Dijkstra+A*超时的原因。
 *		
 *		然后使用Dijkstra算法，过程中同理找出最短路径以及次短路径中最短的 dis[i][0..1]，
 *  dis[i][0..1]即代表到i的最短路径或次短路径已经找到了，置vis[i][0..1]为true，
 *  然后同理用dis[i][0..1]更新相连边的dis[][]，此时要注意递推的过程。
 *  	另l = dis[i][0或1]+edge[j].l
 *  	情况1：l小于dis[edge[j].v][0]。
 *  	情况2：l等于dis[edge[j].v][0]。
 *  	情况3：l大于dis[edge[j].v][0]但小于dis[edge[j].v][1]。
 *  	情况4：l等于dis[edge[j].v][1]。
 *  	利用STL的优先队列，要注意出队列的结点一定要判断vis[i][0..1]是否为真，即dis[i][0..1]是否已经出过一次队了，
 *  防止同一结点的同一路径重复出队。
 *  	若是自己写的优先队列，则因为所有的结点在一开始就已经入队，之后只是更新优先队列中的值，则不会出现重复出队。
 *  (此处WA我的想吐血)。而由于只有1000个结点，即使不用优先队列也可以满足。
 *
 * */
#include<stdio.h>
#include<memory.h>
#include<queue>
#include<vector>
#define INF 1000000005
using namespace std;

int t,n,m,s,f;
struct EDGE
{
	int v,l,next;
}edge[10005];
struct NODE
{
	int v,num;
	long dis;
};
int tot,head[1005];
long dis[1005][2],num[1005][2];
struct cmp
{
	bool operator()(const NODE &t1,const NODE &t2)
	{
		return t1.dis>t2.dis;
	}
};

inline void add(int j,int k,int p,int &tot,EDGE e[],int h[])
{
	e[++tot].v = k,e[tot].l = p,e[tot].next = h[j],h[j] = tot;
}

inline void Dijkstra()
{
	int i;
	NODE node,tmp;
	bool vis[1005][2];
	priority_queue<NODE,vector<NODE>,cmp> queue;

	for(i=1;i<=n;i++)
	{
		dis[i][0] = dis[i][1] = INF;
		vis[i][0] = vis[i][1] = false;
		num[i][0] = num[i][1] = 0;
	}

	node.v = s,node.dis = 0,dis[s][0] = 0,num[s][0] = 1;
	node.num = 0;
	queue.push(node);
	while(!queue.empty())
	{
		node = queue.top();
		queue.pop();
		long u,v;
		u = node.v,v = node.num;
		if(vis[u][v] || node.dis>dis[u][1]) continue;						//一定要判断是否重复出队了。
		vis[u][v]= true;
		for(i=head[node.v];i;i=edge[i].next)
		{
			//if(!vis[edge[i].v][0] && dis[edge[i].v][0]>node.dis+edge[i].l)
			if(dis[edge[i].v][0]>node.dis+edge[i].l)	//情况1，则要更新最短和次短路径的两个记录
			{
				if(dis[edge[i].v][0]<INF)
				{
					dis[edge[i].v][1] = dis[edge[i].v][0];
					num[edge[i].v][1] = num[edge[i].v][0];
				}	
				dis[edge[i].v][0] = node.dis+edge[i].l;
				num[edge[i].v][0] = num[u][v];

				tmp.v = edge[i].v,tmp.dis = dis[edge[i].v][0],tmp.num = 0;
				queue.push(tmp);
				if(dis[edge[i].v][1]<INF)
				{
					tmp.v = edge[i].v,tmp.dis = dis[edge[i].v][1],tmp.num = 1;
					queue.push(tmp);
				}
			//}else if(vis[edge[i].v][0] && dis[edge[i].v][0]==node.dis+edge[i].l)
			}else if(dis[edge[i].v][0]==node.dis+edge[i].l)	//情况2，只需在最短路径上加上上个结点的路径数
			{
				num[edge[i].v][0] += num[u][v];
			//}else if(!vis[edge[i].v][1] && dis[edge[i].v][1]>node.dis+edge[i].l)
			}else if(dis[edge[i].v][1]>node.dis+edge[i].l)	//情况3，要更新次短路径的记录
			{
				dis[edge[i].v][1] = node.dis+edge[i].l;
				num[edge[i].v][1] = num[u][v];
				tmp.v = edge[i].v,tmp.dis = dis[edge[i].v][1],tmp.num = 1;
				queue.push(tmp);
			//}else if(vis[edge[i].v][1] && dis[edge[i].v][1]==node.dis+edge[i].l)
			}else if(dis[edge[i].v][1]==node.dis+edge[i].l)	//情况4，只需在次短路径上加上上个结点的路径数
			{
				num[edge[i].v][1] += num[u][v];
			}
		}
	}
	//while(!queue.empty()) queue.pop();
	return;
}

int main()
{
//	FILE* fin;
//	fin = fopen("d.in","r");
	scanf("%d",&t);
//	fscanf(fin,"%d",&t);
	int i,j,k,p;
	while(t)
	{
		t--;
		memset(edge,0,sizeof(edge));
		memset(head,0,sizeof(head));
		tot = 0;
		scanf("%d%d",&n,&m);
//		fscanf(fin,"%d%d",&n,&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&j,&k,&p);
//			fscanf(fin,"%d%d%d",&j,&k,&p);
			add(j,k,p,tot,edge,head);
		}
		scanf("%d%d",&s,&f);
//		fscanf(fin,"%d%d",&s,&f);

		Dijkstra();
		long ans = num[f][0];
		if(dis[f][0]==dis[f][1]-1)
			ans = num[f][0]+num[f][1];
		printf("%ld\n",ans);
	}
//	fclose(fin);
	return 0;
}