题意：

你知道黑暗城堡有 $n$ 个房间，$m$ 条可以制造的双向通道，以及每条通道的长度。

城堡是树形的并且满足下面的条件：

设 $D_i$ 为如果所有的通道都被修建，第 $i$ 号房间与第 $1$ 号房间的最短路径长度；

而 $S_i$ 为实际修建的树形城堡中第 $i$ 号房间与第 $i$ 号房间的路径长度；

要求对于所有 $1 \le i \le n$，满足 $S_i = D_i$。

求有多少种城堡修建方案，答案对 $2^{31}-1$ 取模。

老师题解：

• 简单来说，题目要求最短路径树的数量。
• 最短路径树是网络的源点到所有结点的最短路径构成的树。
• 先使用 dijkstra 算法处理出 $1$ 号点到每个点的最短路 $d$。
• 当 $d_v = d_u + w(u, v)$ 时，表明 $e(u, v)$ 这条边可作为最 短路径树上的边。
• 对每个点计算出它可作为最短路径树上的边的数量，根据乘法原理，累乘起来就是答案。

我的实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1001
#define MAXM MAXN*MAXN
const int MOD(2147483647);

int n, m, u, v, w, ans(1);
int us[MAXM], vs[MAXM], ws2[MAXM];
int dis[MAXN], cnt[MAXN];

struct Node{
	int u, dis;
	bool operator>(Node b)const{
		return dis > b.dis;
	}
};
priority_queue<Node, vector<Node>, greater<Node>> pq;
struct Edge{
	int v, w;
};
vector<Edge> e[MAXN];
bitset<MAXN> vis;

void dijkstra(int s){
	dis[s] = 0;
	pq.push({s, 0});
	while (!pq.empty()){
		u = pq.top().u;
		pq.pop();
		if (vis.test(u)) continue;
		vis.set(u);
		
		for (auto i: e[u]){
			v = i.v;
			w = i.w;
			if (dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				pq.push({v, dis[v]});
			}
		}
	}
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
	for (int i(1); i<=m; ++i){
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		us[i] = u;
		vs[i] = v;
		ws2[i] = w;
	}
	
	memset(dis, 0x7f, sizeof(dis));
	dijkstra(1);
	
	for (int i(1); i<=m; ++i){
		u = us[i];
		v = vs[i];
		w = ws2[i];
		if (dis[v] == dis[u] + w) ++cnt[u];
	}
	
	for (int i(1); i<=n; ++i){
		if (cnt[i]) ans = (ans * cnt[i]) % MOD;
	}
	cout << ans;

    return 0;
}

求找错或 hack。谢谢！