黑暗城堡

形式化题目

给定一张 $N$ 个点、 $M$ 条边的无向图，边权 $L$ 为正整数，点 $1$ 为根。记 $D[i]$ 为点 $i$ 到点 $1$ 的全图最短路长度。

若从这 $M$ 条边中选出 $N-1$ 条使图连通（即选出一棵生成树），并记树上点 $i$ 到点 $1$ 的路径长度为 $S[i]$ ，求满足

S[i] = D[i] \quad \text{对所有 } 1 \leqslant i \leqslant N

的不同生成树（不同边集）数量，对 $2^{31} - 1$ 取模。

约束： $2 \leqslant N \leqslant 1000$ ， $N - 1 \leqslant M \leqslant N(N-1)/2$ ， $1 \leqslant L \leqslant 100$ 。输入可能包含自环（ $X = Y$ ）。

样例： $N = 3$ ，边为 $(1,2,2)$ 、 $(1,3,1)$ 、 $(2,3,1)$ ，答案为 $2$ 。

正解

思路

为什么要从「每个点的父亲」入手

生成树的个数最大可达 $N^{N-2}$ （ $N = 1000$ 时是天文数字），枚举树或枚举边子集都不可能。但树有一个极其有用的性质：除根以外，每个点在树上的「父亲」（到根路径上的前一个点）唯一。于是「选一棵树」可以被压缩成

$N - 1$ 个点各选一个父亲。

只要这 $N-1$ 个选择能拼成一棵以 $1$ 为根的树，它们就唯一确定一个边集。计数的关键就变成：每个点合法的父亲有哪些？这些选择是否互相独立？

关键观察：父亲必须落在最短路的前驱里

设点 $i \neq 1$ 在树上的父亲是 $p$ ，对应的树边权为 $w$ 。树上到根的距离满足 $S[i] = S[p] + w$ 。题目要求 $S[j] = D[j]$ 对所有 $j$ 成立，代入得

D[i] = D[p] + w.

我们把满足这个等式的边称为紧边。

反过来，如果每个点 $i \neq 1$ 都挑一条紧边当入边，那么沿紧边链往根回溯时 $D$ 每一步都严格变小（因为 $w \geqslant 1$ ），最终必然停在唯一 $D = 0$ 的点，也就是点 $1$ 。所以每个点都能沿入边走到根：图连通；又总共只有 $N-1$ 条边，于是恰好是一棵树，并且树上距离逐段累加正好等于 $D[i]$ 。

这说明「合法树形城堡」与「每个点各挑一条紧边」是一一对应的，而后者每个点的选择互不影响。于是

\text{答案} = \prod_{i=2}^{N} \bigl(\text{与 } i \text{ 相连的紧边条数}\bigr).

紧边怎么数

遍历每条边 $(x, y, w)$ ：若 $D[x] + w = D[y]$ ，就让 $y$ 的可选数 $+1$ ；若 $D[y] + w = D[x]$ ，就让 $x$ 的可选数 $+1$ 。

因为 $w > 0$ ，两个条件不可能同时成立，用 if / elif 即可，每条紧边只会被记到距离更远的那个端点上，不会重复。自环 $x = y$ 时两个条件都变成 $D[x] + w = D[x]$ ， $w \geqslant 1$ 使其恒假，自动被排除——「自环不能当任何点的树边」这件事不必特判。

样例推演

样例的三条边为 $(1,2,2)$ 、 $(1,3,1)$ 、 $(2,3,1)$ ，以 $1$ 为源的最短路是 $D = [0,\ 2,\ 1]$ 。下面标出每条边对哪个端点是紧边：

text

1
2
3
4
5
6
7
8              房间1  D=0
             /          \
      w=2  /              \  w=1      ← 1-2 对房间2 紧（0+2=2）
         /                  \         1-3 对房间3 紧（0+1=1）
     房间2  D=2 ──── w=1 ──── 房间3  D=1
                    ↑
        2-3 只对房间2 紧（D[3]+1 = 2 = D[2]）；
        对房间3 不紧（D[2]+1 = 3 ≠ D[3] = 1）

图中三条边都是紧边，但 $2\text{–}3$ 只算在房间 2 头上：

房间 $i$	$D[i]$	紧边（另一端 $p$ 满足 $D[p] + w = D[i]$ ）	可选父亲数
$2$	$2$	$1 \to 2$ （ $0 + 2$ ）、 $3 \to 2$ （ $1 + 1$ ）	$2$
$3$	$1$	$1 \to 3$ （ $0 + 1$ ）	$1$

表格每一行是一个房间，中间列出所有能当它父亲的边，最后一列给出可选个数。

答案 $2 \times 1 = 2$ ：房间 2 可以选 $1$ 当父亲（此时树边是 $1\text{–}2$ 和 $1\text{–}3$ ），也可以选 $3$ 当父亲（此时树边是 $1\text{–}3$ 和 $2\text{–}3$ ，房间 2 走 $2 \to 3 \to 1$ ，长度也是 $2$ ）。两条路径走法不同、边集不同，都是合法城堡。注意房间 3 不能选 2 当父亲： $D[2] + 1 = 3 \neq D[3] = 1$ ，那条边不是房间 3 的紧边。

求 $D[]$

边权为正，用堆优化 Dijkstra， $O((N + M) \log N)$ 。实现上把堆元素打包成一个整数 (距离 << 10) | 编号：低 10 位专放编号（ $N \leqslant 1000 < 2^{10}$ ），于是整数的大小比较就是「先比距离、再比编号」，省掉元组比较的开销。

代码

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/**
 * 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-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 城堡：Dijkstra 求最短路，再数每个点的“紧边”条数，方案数是紧边条数之积
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

const ll MOD = (1LL << 31) - 1; // 答案要模的数 2^31 - 1
const ll INF = 1LL << 60;

struct Arc { // 邻接表里的一条出边
    int v;
    ll w;
};

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) {
        return 0;
    }
    vector<vector<Arc> > adj(n);
    vector<int> ex(m), ey(m);
    vector<ll> ew(m);
    for (int i = 0; i < m; i++) {
        int x, y;
        ll w;
        scanf("%d %d %lld", &x, &y, &w);
        ex[i] = x - 1;
        ey[i] = y - 1;
        ew[i] = w;
        Arc a1 = {y - 1, w}, a2 = {x - 1, w};
        adj[x - 1].push_back(a1); // 通道双向
        adj[y - 1].push_back(a2);
    }

    // 堆里放 (距离, 编号) 的对，距离小的先出队
    vector<ll> dist(n, INF);
    dist[0] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    pq.push(make_pair(0LL, 0));
    while (!pq.empty()) {
        pair<ll, int> top = pq.top();
        pq.pop();
        ll d = top.first;
        int u = top.second;
        if (d > dist[u]) {
            continue; // 已被更短的距离取代
        }
        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i].v;
            ll nd = d + adj[u][i].w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push(make_pair(nd, v));
            }
        }
    }

    // 紧边：D[另一端] + w 恰好等于 D[自己]；它只会算到距离更远的那一端
    vector<ll> tight(n, 0);
    for (int i = 0; i < m; i++) {
        if (dist[ex[i]] + ew[i] == dist[ey[i]]) {
            tight[ey[i]]++;
        } else if (dist[ey[i]] + ew[i] == dist[ex[i]]) {
            tight[ex[i]]++;
        }
    }

    ll ans = 1; // 每个房间 2..N 独立挑一条紧边当树边
    for (int v = 1; v < n; v++) {
        ans = ans * tight[v] % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

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
67
68
69
70
71
72
73
74
75
76
77
78#!/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-10-02 00:10
# update_at: 2026-10-02 00:10

import sys
from array import array
from heapq import heappop, heappush
from math import prod

MOD = (1 << 31) - 1  # 答案要模的数 2^31 - 1
SHIFT = 10           # 打包用：低 10 位专放房间编号（N ≤ 1000 < 2^10），高位放边权
ID_MASK = (1 << SHIFT) - 1
INF = 1 << 60        # 不可达的距离哨兵，足够大，不会和真实距离混淆


def shortest_distances(n: int, adj: list[array]) -> list[int]:
    """求 1 号房间到每个房间的最短距离 D[]。

    堆里把 (距离, 编号) 打包成一个整数，低位留给编号，于是整数序就是距离序，
    省掉元组比较；距离相同也不会出错——编号只用来区分不同的房间。
    """
    dist = [INF] * n
    dist[0] = 0
    pq = [0]                                    # 源点：距离 0、编号 0
    while pq:
        item = heappop(pq)
        d, u = item >> SHIFT, item & ID_MASK
        if d > dist[u]:
            continue                            # 这项已被更短的距离取代
        for packed in adj[u]:
            v, nd = packed & ID_MASK, d + (packed >> SHIFT)
            if nd < dist[v]:                    # 必须处理「变小」分支，不能只处理首次到达
                dist[v] = nd
                heappush(pq, (nd << SHIFT) | v)
    return dist


def tight_edge_counts(n: int, edges: array, dist: list[int]) -> list[int]:
    """数每个房间有几条「紧边」：D[另一端] + w 恰好等于 D[自己]。

    同一条紧边只会算到它「距离更远」的那个端点上：边权为正，两个方向不可能同时成立。
    自环两端都是自己，D[x] + w 严格大于 D[x]，自然被排除。
    """
    tight = [0] * n
    for i in range(0, len(edges), 3):
        x, y, w = edges[i], edges[i + 1], edges[i + 2]
        if dist[x] + w == dist[y]:
            tight[y] += 1
        elif dist[y] + w == dist[x]:
            tight[x] += 1
    return tight


def solve() -> None:
    # 按空白分词而不是按行拆：题面保证的是空白分隔的数字，换行位置并不固定。
    # 生成器逐行惰性读取，不会把整份输入同时留在内存里。
    tokens = (int(t) for line in sys.stdin.buffer for t in line.split())
    n, m = next(tokens), next(tokens)

    # M 最大约 5×10^5，邻接表用 array('i') 装打包好的整数：每个邻居只占 4 字节，
    # 比 Python 列表省一个数量级的内存，遍历时也不必反复装箱。
    adj: list[array] = [array('i') for _ in range(n)]
    edges = array('i')                          # 原始边表，最后数紧边时还要再扫一遍
    for _ in range(m):
        x, y, w = next(tokens) - 1, next(tokens) - 1, next(tokens)
        edges.extend((x, y, w))
        adj[x].append((w << SHIFT) | y)         # 通道双向，两边都要挂
        adj[y].append((w << SHIFT) | x)

    # 每个房间 2..N 独立挑一条紧边当树边，方案数就是可选条数的乘积
    print(prod(tight_edge_counts(n, edges, shortest_distances(n, adj))[1:]) % MOD)


if __name__ == "__main__":
    solve()

复杂度

时间：Dijkstra $O((N + M) \log N)$ ，统计紧边 $O(M)$ ，求乘积 $O(N)$ ，总计 $O(M \log N)$ 。
空间：邻接表与堆 $O(N + M)$ ，距离数组与计数组 $O(N)$ 。

在最大测例（ $N = 1000$ 、 $M = 499500$ ）上 Python 实测约 0.35 s、峰值内存约 51 MB。内存上有两个坑：一次性 read().split() 读入、以及用 list 装邻接表，都会让 peak RSS 达 $230$ MB 以上，远超 128 MB 限制。改成逐行分词（不把整份输入与 token 列表同时留在内存）

邻接表用 array('i') 存打包整数（每邻居 4 字节而非约 36 字节）后降到约 51 MB。

总结

题目问的是「生成树计数」，但真正起作用的只有全图最短路 $D[]$ ：

树上每个点到根的路径唯一，所以每个点只需选一个父亲；
$S[i] = D[i]$ 等价于「选一条紧边 $D[p] + w = D[i]$ 」；
由于 $w > 0$ ，紧边严格从低 $D$ 指向高 $D$ ，任意一组选择自动拼成树，且各点独立；
于是答案就是「每个点紧边数」的乘积。

一旦看出第 2 步，题目就从指数级的枚举退化成一次 Dijkstra 加一遍边表扫描。这道题也提醒我们：「最短路前驱」本身就是一张按 $D$ 分层的 DAG，它的入边计数往往就是答案。

目录