黑暗城堡

形式化题目

给定一个包含 $N$ 个顶点和 $M$ 条无向带权边的连通图，所有边权满足 $l \geqslant 1$ 。记 $D_i$ 为图上从源点 $1$ 到顶点 $i$ 的最短路径长度。

求原图的生成树（以 $1$ 为根）的数量，使得树上节点 $i$ 到根节点 $1$ 的距离 $S_i$ 严格等于 $D_i$ （对所有 $1 \leqslant i \leqslant N$ ）。答案对 $2^{31} - 1$ 取模。

正解

思路

1. 问题性质转化

题目所求的树即为最短路径生成树（Shortest Path Tree, SPT）。在一棵以 $1$ 号节点为根的树中，每个非根节点 $u \in \{2, 3, \dots, N\}$ 恰好有一个父节点 $p_u$ 。要使树上每个节点到根的距离均等于最短距离，即 $S_u = D_u$ ，对于树上的每一条父子边 $(p_u, u)$ 必须满足：

D_{p_u} + w(p_u, u) = D_u

由于题目中所有的边权均为正数（ $l \geqslant 1$ ），若某个相邻节点 $v$ 满足 $D_v + w(v, u) = D_u$ ，则必有：

D_v < D_u

这意味着：

如果每个非根节点 $u$ 从所有满足 $D_v + w(v, u) = D_u$ 的相邻节点中任选一个作为父节点，得到的图包含 $N$ 个节点和 $N-1$ 条有向边。
沿着任意节点的父节点指针不断回溯，节点的最短距离 $D$ 严格单调递减。在有限集合上，严格单调递减的序列绝不可能成环，且必然能终止于全局最小值 $D_1 = 0$ （即根节点 $1$ ）。
因此，这 $N-1$ 条边必然构成一棵以 $1$ 为根的树，并且满足所有节点的 $S_i = D_i$ 。

2. 乘法原理计数

由于每个节点 $u$ 对父节点的选取仅依赖于其与前驱节点的距离关系，与其他非根节点的决策完全独立，因此不同节点的父节点选取可以独立进行。

设非根节点 $u$ 可选的合法前驱父节点数量为 $c_u$ ：

c_u = \sum_{(v, u) \in E} [D_v + w(v, u) = D_u]

根据乘法原理，满足条件的最短路径生成树总数即为：

\text{ans} = \prod_{u=2}^N c_u \pmod{2^{31}-1}

3. 算法流程

使用堆优化的 Dijkstra 算法，以顶点 $1$ 为源点计算到达所有顶点的最短路 $D_u$ 。
遍历每个节点 $u \in \{2, \dots, N\}$ ，统计其所有相连的边中有多少条满足 $D_v + w = D_u$ 。
将所有节点的备选边数相乘，并对 $2^{31}-1$ 取模即可。

样例图解

以输入样例为例： $4$ 个节点， $6$ 条边，边权分别为 $(1,2,1), (1,3,2), (1,4,3), (2,3,1), (2,4,2), (3,4,1)$ 。

graph LR
    1((1)) -- 1 --> 2((2))
    1((1)) -- 2 --> 3((3))
    1((1)) -- 3 --> 4((4))
    2((2)) -- 1 --> 3((3))
    2((2)) -- 2 --> 4((4))
    3((3)) -- 1 --> 4((4))

经过 Dijkstra 算法计算，源点 $1$ 到各点的最短距离为：

$D_1 = 0$
$D_2 = 1$
$D_3 = 2$
$D_4 = 3$

检查各非根节点的前驱选择情况：

节点 $2$ （ $D_2=1$ ）：前驱只能是节点 $1$ （边长 $1$ ），可选数 $c_2 = 1$ 。
节点 $3$ （ $D_3=2$ ）：
- 节点 $1$ ： $D_1 + 2 = 0 + 2 = 2 = D_3$ （有效）
- 节点 $2$ ： $D_2 + 1 = 1 + 1 = 2 = D_3$ （有效）
- 共有 $2$ 种选择，故 $c_3 = 2$ 。
节点 $4$ （ $D_4=3$ ）：
- 节点 $1$ ： $D_1 + 3 = 0 + 3 = 3 = D_4$ （有效）
- 节点 $2$ ： $D_2 + 2 = 1 + 2 = 3 = D_4$ （有效）
- 节点 $3$ ： $D_3 + 1 = 2 + 1 = 3 = D_4$ （有效）
- 共有 $3$ 种选择，故 $c_4 = 3$ 。

总方案数为：

\text{ans} = c_2 \times c_3 \times c_4 = 1 \times 2 \times 3 = 6

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:14
# update_at: 2026-09-30 14:14

import heapq
import sys

MOD = (1 << 31) - 1
INF = float("inf")


def dijkstra(n: int, adj: list[list[tuple[int, int]]]) -> list[int]:
    """计算源点 1 到各房间的最短距离列表（1-indexed）。"""
    dist = [INF] * (n + 1)
    dist[1] = 0
    pq = [(0, 1)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist


def count_parent_choices(u: int, adj: list[list[tuple[int, int]]], dist: list[int]) -> int:
    """统计房间 u 可选的树上前驱父节点数量。"""
    return sum(1 for v, w in adj[u] if dist[v] + w == dist[u])


def count_shortest_path_trees(n: int, adj: list[list[tuple[int, int]]]) -> int:
    """按乘法原理计算合法的最短路径生成树方案数。"""
    dist = dijkstra(n, adj)
    ans = 1
    for u in range(2, n + 1):
        choices = count_parent_choices(u, adj, dist)
        ans = (ans * choices) % MOD
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:
        return
    m = next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        adj[u].append((v, w))
        adj[v].append((u, w))

    ans = count_shortest_path_trees(n, adj)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:57
 * update_at: 2026-10-05 03:57
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;
const int MAXM = 500005; // N(N-1)/2 上界，双向边所以存边数翻倍后仍够用
const ll MOD = (1LL << 31) - 1;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

// 边权 l <= 200，距离最大约 1000*200 = 2e5，用 ll 稳妥
int n, m;
int head[MAXN], nxt[MAXM * 2], to[MAXM * 2], w[MAXM * 2], edge_cnt; // 链式前向星存无向图
ll dist_[MAXN]; // dist_[i] 表示 1 号房间到 i 号房间的最短距离 D_i
bool vis[MAXN]; // Dijkstra 中该点最短路是否已确定
ll ans;         // 方案数，对 2^31 - 1 取模

struct HeapNode {
    ll d; // 当前距离
    int u; // 节点编号
    // 小根堆按距离比较
    bool operator<(const HeapNode &b) const {
        return d > b.d;
    }
};

// 加一条无向边 u <-> v，长度 len
void add_edge(int u, int v, int len) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = len;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 堆优化 Dijkstra，求 1 到所有点的最短距离
void dijkstra() {
    for (int i = 1; i <= n; i++) {
        dist_[i] = INF;
        vis[i] = false;
    }
    dist_[1] = 0;
    priority_queue<HeapNode> q; // 小根堆，堆顶是当前距离最小的点
    q.push({0, 1});

    while (!q.empty()) {
        HeapNode top = q.top();
        q.pop();
        int u = top.u;
        if (vis[u]) continue; // 已确定最短路的点直接跳过
        vis[u] = true;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (dist_[u] + w[i] < dist_[v]) {
                dist_[v] = dist_[u] + w[i];
                q.push({dist_[v], v});
            }
        }
    }
}

// 统计节点 u 可选的合法前驱父节点数量 c_u
ll count_choice(int u) {
    ll cnt = 0;
    for (int i = head[u]; i != 0; i = nxt[i]) {
        int v = to[i];
        // v 能作为 u 的父节点当且仅当 D_v + w(v,u) = D_u
        if (dist_[v] + w[i] == dist_[u]) cnt++;
    }
    return cnt;
}

void solve() {
    dijkstra();
    // 乘法原理：每个非根节点独立选父节点，方案数连乘
    ans = 1;
    for (int u = 2; u <= n; u++) {
        ans = ans * count_choice(u) % MOD;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, l;
        cin >> x >> y >> l;
        add_edge(x, y, l);
        add_edge(y, x, l);
    }
    solve();

    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(M \log N)$ 。Dijkstra 堆优化耗时 $\mathcal{O}(M \log N)$ ；遍历各节点的所有入边统计候选前驱耗时 $\mathcal{O}(N + M)$ ；方案数乘法累乘耗时 $\mathcal{O}(N)$ 。整体耗时受 Dijkstra 支配，对于 $N \leqslant 1000, M \leqslant 5 \times 10^5$ 的数据规模，可以在毫秒级内完成。
空间复杂度： $\mathcal{O}(N + M)$ 。用于存储邻接表、距离数组以及优先队列。

总结

最短路径生成树（SPT）计数问题的关键在于利用正权边所保证的拓扑偏序性：合法的树边只能由最短距离较小的点连向最短距离较大的点。这样，整棵树的构建被解耦为了每个非根节点独立选择唯一的入边前驱，从而将复杂的全图树形计数简化为利用乘法原理计算各点可选入边的连乘积。

目录

形式化题目

正解

思路

1. 问题性质转化

2. 乘法原理计数

3. 算法流程

样例图解

代码

复杂度

总结