rt，样例都没过。。。

题目

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<20+5];
inline int read(){
unsigned int x=0;
char c=gc();
while(!isdigit(c)){
c=gc();
}while(isdigit(c)){
x=x*10+(c^48);
c=gc();
}return x;
}

const int N = 1005, M = N * (N - 1) / 2, mod = 2147483647;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int cnt[N], res;
int dist[N], g[N][N];
bool st[N];

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()
{
	memset(dist, 0x3f, sizeof dist);
	queue<int> q;
	q.push(1);
	st[1] = 1;
	
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		st[t] = 0;
		for (int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[t] + w[i] < dist[j])
			{
				dist[j] = dist[t] + w[i];
				if (!st[j])
				{
					q.push(j);
					st[j] = 1;
				}
			}
		}
	}
}

int main()
{
	memset(g, -1, sizeof g);
	memset(h, -1, sizeof h);
	n = read(), m = read();
	for (int i = 1; i <= m; i ++ )
	{
		int a, b, c;
		a = read(), b = read(), c = read();
		g[a][b] = g[b][a] = c;
		add(a, b, c), add(b, a, c);
	}
	
	spfa();
	
	for (int i = 1; i <= n; i ++ )
	  for (int j = 1; j <= n; j ++ )
	    if (g[i][j] != -1 && dist[i] + g[i][j] == dist[j]) cnt[j] ++;
	
	res = 1;
	for (int i = 1; i <= n; i ++ ) if (cnt[i]) res *= cnt[i], res %= mod;
	
	printf("%d\n", res);
	return 0;
}