#include <algorithm>  
#include <bitset>  
#include <cctype>  
#include <cerrno>  
#include <clocale>  
#include <cmath>  
#include <complex>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <ctime>  
#include <deque>  
#include <exception>  
#include <fstream>  
#include <functional>  
#include <limits>  
#include <list>  
#include <map>  
#include <iomanip>  
#include <ios>  
#include <iosfwd>  
#include <iostream>  
#include <istream>  
#include <ostream>  
#include <queue>  
#include <set>  
#include <sstream>  
#include <stdexcept>  
#include <streambuf>  
#include <string>  
#include <utility>  
#include <vector>  
#include <cwchar>  
#include <cwctype>  
#include <stack>  
#include <limits.h>
using namespace std;
#define MAXN 2010
#define MAXM 20010
const int INF = 2e9;

struct edge
{
		int to,w,nxt;
} e[MAXM << 1];

int i,n,m,ans,tot,tmp,val,shortest,S,T,TC;
int head[MAXN],rhead[MAXN],u[MAXM],v[MAXM],w[MAXM],
		dista[MAXN],distb[MAXN],cnta[MAXN],cntb[MAXN];

inline void addedge(int u,int v,int w)
{
		tot++;
		e[tot] = (edge){v,w,head[u]};
		head[u] = tot;
}
inline void addredge(int u,int v,int w)
{
		tot++;
		e[tot] = (edge){v,w,rhead[u]};
		rhead[u] = tot;
}
inline void spfa1(int s)
{
		int i,l,r,u,v,w;
		static int q[MAXN];
		static bool inq[MAXN];
		for (i = 1; i <= n; i++) 
		{
				dista[i] = INF;
				inq[i] = false;
		}
		q[l = r = 1] = s;
		inq[s] = true;
		dista[s] = 0; 
		while (l <= r)
		{
				u = q[l];
				l++;
				inq[u] = false;
				for (i = head[u]; i; i = e[i].nxt)
				{
						v = e[i].to;
						w = e[i].w;
						if (dista[u] + w < dista[v])
						{
								dista[v] = dista[u] + w;
								if (!inq[v])
								{
										inq[v] = true;
										q[++r] = v;
								}
						} 
				}
		}
}
inline void spfa2(int s)
{
		int i,l,r,u,v,w;
		static int q[MAXN];
		static bool inq[MAXN];
		for (i = 1; i <= n; i++)
		{
				distb[i] = INF;
				inq[i] = false;
		}
		q[l = r = 1] = s;
		distb[s] = 0; 
		inq[s] = true;
		while (l <= r)
		{
				u = q[l];
				l++;
				inq[u] = false;
				for (i = rhead[u]; i; i = e[i].nxt)
				{
						v = e[i].to;
						w = e[i].w;
						if (distb[u] + w < distb[v])
						{
								distb[v] = distb[u] + w;
								if (!inq[v])
								{
										inq[v] = true;
										q[++r] = v;
								}
						} 
				}
		}
}
inline int dp1(int u)
{
		int i,v,w;
		if (cnta[u] != -1) return cnta[u];
		if (u == S) return cnta[u] = 1;
		cnta[u] = 0;
		for (i = rhead[u]; i; i = e[i].nxt)
		{
				v = e[i].to;
				w = e[i].w;
				if (dista[v] + w == dista[u]) cnta[u] += dp1(v);
		}
		return cnta[u];
}
inline int dp2(int u)
{
		int i,v,w;
		if (cntb[u] != -1) return cntb[u];
		if (u == T) return cntb[u] = 1;
		cntb[u] = 0;
		for (i = head[u]; i; i = e[i].nxt)
		{
				v = e[i].to;
				w = e[i].w;
				if (dista[u] + w == dista[v]) cntb[u] += dp2(v);
		}
		return cntb[u];
}
int main() 
{
		
		scanf("%d",&TC);
		while (TC--)
		{
				scanf("%d%d",&n,&m);
				tot = 0;
				for (i = 1; i <= n; i++) 
				{
						head[i] = rhead[i] = 0;
						cnta[i] = cntb[i] = -1;
				}
				for (i = 1; i <= m; i++)
				{
						scanf("%d%d%d",&u[i],&v[i],&w[i]);
						addedge(u[i],v[i],w[i]);
						addredge(v[i],u[i],w[i]);
				}		
				scanf("%d%d",&S,&T);
				spfa1(S);
				spfa2(T);
				for (i = 1; i <= n; i++) dp1(i);
				for (i = 1; i <= n; i++) dp2(i);
				shortest = dista[T];
				ans = cnta[T];
				for (i = 1; i <= m; i++)
				{
						tmp = dista[u[i]] + w[i] + distb[v[i]];
						if (dista[u[i]] + w[i] == dista[v[i]] + 1 && tmp == shortest + 1) ans += cnta[u[i]] * cntb[v[i]];
				}
				printf("%d\n",ans);
		}
		
		return 0;
	
}

• Re:spfa 32ms~ (4203) Fangs 2019-06-12 19:19:57