记录编号	563402	评测结果	AAAAAAAAAA
题目名称	3464.[Nescafé II]黑暗城堡	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.189 s
提交时间	2021-08-06 12:37:19	内存使用	5.58 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
const int maxn = 1005;
const long long mod = (1ll << 31) - 1;
const int maxm = 1000005;
int head[maxn],ver[maxm],nxt[maxm],cost[maxm];
int cnt;
bool vis[maxn];
int dis[maxn];
typedef pair<int,int> pa;
priority_queue<pa,vector<pa>,greater<pa> > q;
void add(int u,int v,int t) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	cost[cnt] = t;
	head[u] = cnt;
	return ;
}
int n,m,rk[maxn];
int  a[maxn][maxn];
bool cmp(int a,int b) {
	return dis[a] < dis[b];
}
void dijkstra(int s) {
	memset(vis , false , sizeof(vis));
	memset(dis , 0x3f , sizeof(dis));
	dis[s] = 0;
	q.push(make_pair(dis[s] , s));
	while(!q.empty()) {
		int u = q.top().second;
		q.pop();
		if(vis[u])continue ;
		vis[u] = true;
		for(int i = head[u];i;i = nxt[i]) {
			int v = ver[i],w = cost[i];
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push(make_pair(dis[v] , v));
			}
		}
	}
	return ;
}
int main() {
	freopen("darkcastle.in","r",stdin);
	freopen("darkcastle.out","w",stdout);
	scanf("%d%d",&n,&m);
	int u,v,t;
	memset(a , 0x3f , sizeof(a));
	for(int i = 1;i <= m;++ i) {
		scanf("%d%d%d",&u,&v,&t);
		add(u , v , t);
		add(v , u , t);
		a[u][v] = a[v][u] = min(a[u][v] , t); 
	}
	dijkstra(1);
	for(int i = 1;i <= n;++ i)rk[i] = i,a[i][i] = 0;
	sort(rk + 1 , rk + 1 + n , cmp);
	long long ans = 1; 
	for(int i = 2;i <= n;++ i) {
		int t = rk[i];
		cnt = 0;
		for(int j = 1;j < i;++ j) {
			int p = rk[j];
			if(dis[t] == dis[p] + a[p][t]) {
				++ cnt;
			}
		} 
		ans = 1ll * ans * cnt % mod;
	}
	printf("%lld\n",ans);
	fclose(stdin) ;
	fclose(stdout);
	return 0;
}