企业官网建设流程全解析

洛谷P1144，标准的题目名叫“最短路计数”，是我刷图论入门题单时绕不开的一道题。题目本身不复杂：给你一张可能有重边和自环的无向无权图，从点1出发，问到达每个点的最短路径一共有多少条，结果对100003取模。但这道题在洛谷的讨论区里常年热度不减，评论区总能见到“为什么BFS就能计数？”“重边要不要特判？”这类问题，甚至我自己第一次写就漏掉了等距更新的情况。

这篇不是把官方题解复述一遍，而是想把我从抄代码到真正想明白的全过程拆开：为什么最短路计数本质是个动态规划，BFS为什么恰好能给出合法转移顺序，链式前向星和Java怎么写才不爆内存，以及那些提交了五六次才发现的小坑。适合刚学完BFS和基础图论、准备刷洛谷题单或校赛的读者。

1. 题目到底在问什么：先看清这题长什么样

1.1 输入、输出与真正的数据规模

输入格式非常常规：第一行两个正整数 n、m，表示点数和边数；接下来 m 行，每行两个正整数 u、v，表示一条无向边。输出要求从 1 号点出发，第 i 行输出到 i 号点的最短路条数对 100003 取模后的值。如果从 1 号点无法到达 i，那么输出 0。

有个新手经常会问的问题，正好可以在这里说清楚：在洛谷提交代码时，数据是评测系统通过标准输入喂给程序的，你不需要自己去读本地文件，更不需要关心“数据放在哪个文件夹”。你只要用标准输入把数据读完，用标准输出把答案打印出来，剩下的全部交给评测机。所以别在这个问题上浪费哪怕一分钟。

再说数据范围。我印象中洛谷这道题的数据范围很“大胃王”，N 和 M 可以到百万量级，至少不是那种让你随随便便开邻接矩阵的小图。这意味着两件事：第一，邻接矩阵想都不用想，O(n²) 内存直接爆炸；第二，输入输出量非常大，如果你用不关同步的 cin 加上 endl，大概率会收获一个 TLE。后文我会专门说怎么在这一步上省时间。

1.2 这题难在哪：不是求最短，而是数最短

如果只求最短长度，那就是最基础的 BFS：维护一个 dist 数组，第一次访问到某个点时就赋值，最后输出 dist[i] 即可。但这道题多了一个字：“条数”。这样就要求我们不能只记“最短有多短”，还得记“最短的来路有几条”。

举个例子，点 1 到点 3 的最短距离是 2，但是走法可能有两种：1→2→3 和 1→4→3。只要这两条路的长度都是 2，那么在答案里，cnt[3] 就应该是 2。如果两条路里有公共前缀，比如 1→2 有两种走法，之后 2→3 只有一条，那么 cnt[3] 应该是 2 而不是 1，因为两条完整路径仍然是不同的路径。

这个“计数”的要求，是整道题的核心门槛。很多人第一反应是：我 BFS 跑一遍，把所有最短路径都枚举出来不就行了？对于小图可以，但百万级别的图里路径数量是指数级增长的，你根本枚举不完。所以必须用动态规划式的累加来统计，而不是真的去把路径一条一条列出来。

1.3 题目在算法题单里的位置

如果你看过洛谷的动态规划题单，会发现偶尔有人把 P1144 也放进去讨论。它明明是一道图论题，为什么能跟 DP 扯上关系？因为最短路计数本身就是“在有向无环图上的路径计数”，只是这个 DAG 不是题目直接给你的，而是由“距离源点更近”这个关系隐式定义的。

换句话说，你可以把每个点理解成一层一层推进的状态，从点 1 开始，距离为 1 的点由距离为 0 的点转移过来，距离为 2 的点由距离为 1 的点转移过来。这个过程和图上的拓扑排序非常相似，只不过拓扑序恰好由 BFS 的访问顺序代替了。所以它既出现在“图论最短路”题单里，也经常被拿来当作“计数 DP”的入门例子。理解了这一点，后面很多题你都会豁然开朗。

2. 为什么最短路计数本质上是个DP

2.1 先写出那个核心方程

不管是 BFS 还是 Dijkstra，最短路计数都逃不开下面这个转移逻辑：

对于一条从 u 出发到达 v 的边，如果当前记录的最短距离满足 dist[v] == dist[u] + 1，那么说明“从 1 到 u 的最短路，再接上 u→v 这条边”，就是一条从 1 到 v 的最短路。于是应该有：

cnt[v] += cnt[u]

如果 v 还没有被访问过，也就是说 dist[v] 还是无穷大（或者 -1），那么第一个发现它的 u 会确定一个最短距离，此时 cnt[v] = cnt[u]。之后再遇到其他 u' 满足 dist[v] == dist[u'] + 1，就让 cnt[v] 继续累加。

这个方程看起来平平无奇，但它就是整道题的灵魂。你需要先知道所有靠近源点的点的 cnt，才能算出当前点的 cnt。这不就是典型的动态规划状态转移吗？只是它的转移方向被“到源点的距离”严格排好了序，不允许有环。

2.2 为什么BFS天然满足转移顺序

BFS 在无向无权图里是按“层”扩展的：先把距离为 1 的所有点访问完，再访问距离为 2 的所有点，依次类推。这个特性保证了：一个点第一次被访问到时，它拿到的距离就是全局最短距离。因为在无权图中，不可能存在一条路径比 BFS 先到达的层数还要短。

有了这个保证之后，计数就顺理成章了。当你在处理某一个点时，所有可能向它提供最短路径的前驱点，距离一定比它小 1，而这些前驱点早就已经出队、早就已经把自己的 cnt 计算完了。于是当前点可以放心地累加所有前驱点的 cnt，不会出现“某个前驱还没算好就急着给当前点加数”的情况。

你可以把这个过程理解成发传单：点 1 手上有 1 张传单，它发给每个邻居，每个邻居拿到传单后，再按自己的传单张数复制给下一层。因为 BFS 保证传单永远是从近处往远处传递，没人会在传单还没到齐的时候私自统计，所以最后每个人手里的传单数量就是正确的方案数。

2.3 为什么DFS直接做容易出错

有些初学者会想：BFS 能做，DFS 是不是也能做？我搜一遍图，遇到满足 dist[v] == dist[u] + 1 就计数，不就行了？问题是 DFS 的访问顺序不是按距离递增的。

举个例子，DFS 可能先从一条长路径绕到 v，此时给 v 赋了一个比较大的 dist；之后再从一条更短路径绕回 v，你确实可以更新 dist[v]，但问题是之前已经基于那个错误的大 dist，给 v 的后续节点传递过 cnt 了。虽然你可以强行回溯重新计算，但在一个百万节点、可能存在环的图里，这种反复更新的复杂度完全不可控，而且极容易重复计数。所以最短路计数题基本不会用 DFS 硬搜，而是用 BFS 或 Dijkstra 这一类“能保证按距离递增顺序处理节点”的算法。

3. 完整实现：从邻接表设计到能交的代码

3.1 先解决存储：为什么用链式前向星而不是vector嵌套

看到 n 和 m 都是百万量级，第一件事就是选存储结构。

用邻接矩阵？一个 n×n 的二维数组，哪怕每个元素只占 1 字节，1e6×1e6 那也是 1TB 量级，想都别想。用 vector<vector >？理论上可行，但每个 vector 对象本身就有不小的内存开销。假设 n=1e6，光 100 万个 vector 对象就可能吃掉 24MB 左右，再加上存储边关系的 int，整体大约 40MB 起步，虽然勉强能过，但如果你对内存比较紧张，或者遇到频繁 push_back 导致的动态扩容，还是有点心疼。

链式前向星是我在竞赛里更喜欢的方案。它本质上是静态链表：head[u] 指向 u 的第一条边在 edge 数组里的下标，edge 数组里的每个元素记录两个信息：这条边通向哪个点 to，以及同起点的下一条边叫什么 next。加边时用头插法，新边永远插在 head[u] 的位置。整张图只需要两个数组，内存非常紧凑。

3.2 C++代码：BFS计数模版

下面这份是我实际提交时用的版本。数组大小按 N≤10^6、M≤2×10^6 来开，如果你确认题目数据范围更小，适当缩小也可以，但开大了并不影响正确性，只是多用一点内存。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; const int MAXM = 2000005; const int MOD = 100003; struct Edge { int to, next; } edge[MAXM << 1]; // 无向边要存两条方向，所以开两倍 int head[MAXN], tot; int dist[MAXN], cnt[MAXN]; int q[MAXN], headq, tailq; // 直接用数组模拟队列，比 std::queue 更省内存也更稳 inline void addEdge(int u, int v) { edge[++tot] = {v, head[u]}; head[u] = tot; } // 快读：输入量很大时，getchar 手写解析比 scanf 还要快一截 inline int read() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x; } int main() { int n = read(), m = read(); for (int i = 0; i < m; i++) { int u = read(), v = read(); addEdge(u, v); addEdge(v, u); } memset(dist, -1, sizeof(dist)); dist[1] = 0; cnt[1] = 1; q[tailq++] = 1; while (headq < tailq) { int u = q[headq++]; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (dist[v] == -1) { // 第一次到达，直接继承当前点的方案数 dist[v] = dist[u] + 1; cnt[v] = cnt[u]; q[tailq++] = v; } else if (dist[v] == dist[u] + 1) { // 距离相等，说明发现新的最短路，累加方案数 cnt[v] = (cnt[v] + cnt[u]) % MOD; } } } for (int i = 1; i <= n; i++) { printf("%d\n", cnt[i]); } return 0; }

这里有个顺序问题我特别说一下：判断dist[v] == -1必须在前，判断等距累加在后。原因是当 v 第一次被访问时，它的 dist 会从 -1 变成某个具体值。如果你把等距判断写在前面，第一次访问时 dist[v] 等于 -1，而 -1 显然不等于 dist[u] + 1，程序就会跳过累加，直接走到dist[v] == -1分支里，看起来好像没错。但如果有重边，场景会变得非常微妙。总之，这个 if 分支的顺序就是算法正确性的一部分，不是随便写的。

3.3 如果用Java写要注意什么

Java 写这种大输入量的题，最怕的就是 Scanner。StreamTokenizer 或者自定义快读是必需品。其次，邻接表别用 ArrayList<ArrayList > 嵌套，内存开销大而且慢，更推荐直接用三个一维数组模拟链式前向星。

import java.io.*; import java.util.*; public class Main { static final int MOD = 100003; static int[] head, to, nxt; static int tot; static void add(int u, int v) { to[++tot] = v; nxt[tot] = head[u]; head[u] = tot; } public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int m = (int) in.nval; head = new int[n + 1]; to = new int[2 * m + 5]; nxt = new int[2 * m + 5]; for (int i = 0; i < m; i++) { in.nextToken(); int u = (int) in.nval; in.nextToken(); int v = (int) in.nval; add(u, v); add(v, u); } int[] dist = new int[n + 1]; int[] cnt = new int[n + 1]; Arrays.fill(dist, -1); dist[1] = 0; cnt[1] = 1; Queue<Integer> q = new ArrayDeque<>(); q.add(1); while (!q.isEmpty()) { int u = q.poll(); for (int e = head[u]; e != 0; e = nxt[e]) { int v = to[e]; if (dist[v] == -1) { dist[v] = dist[u] + 1; cnt[v] = cnt[u]; q.add(v); } else if (dist[v] == dist[u] + 1) { cnt[v] = (cnt[v] + cnt[u]) % MOD; } } } StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { sb.append(cnt[i]).append('\n'); } System.out.print(sb); } }

Java 版本里我保留了 ArrayDeque 而不是 LinkedList，因为在大量出队入队的场景下 ArrayDeque 的常数更小。输出用 StringBuilder 一次性拼好，也比逐行 System.out.println 快很多。

4. 提交五次才过的坑：自环、重边、取模与输入

4.1 自环到底要不要特判

自环就是 u 到 u 的一条边。很多人的第一反应是：这会不会让 cnt[u] 自己加自己，导致答案爆炸？实际上不会。因为我们要判断的是dist[v] == dist[u] + 1，而 v 和 u 是同一个点时，dist[u] 不可能等于 dist[u] + 1。所以自环在 BFS 计数里天然被忽略，不需要额外特判。

就算自环出现在起点 1 上，dist[1] 是 0，检查到自环时条件不成立，cnt[1] 不会被改动。所以你在实现时完全不用管自环，放心让 BFS 去遍历即可。

4.2 重边带来的“看似重复”其实是正确行为

重边的坑更隐蔽。假设 u 和 v 之间有两条平行边，你在遍历 u 的邻接表时，第一条边让 v 第一次入队，dist[v] 被赋为 dist[u]+1，cnt[v] = cnt[u]。紧接着第二条边又指向 v，此时 dist[v] 已经是 dist[u]+1，于是进入等距分支，cnt[v] 再次加了一次 cnt[u]。

这不就重复计数了吗？答案是：没有。因为这两条边是两条不同的边，从 u 到 v 的“走法”本来就因为边的不同而不同。比如 u 和 v 之间修了两条路，你从 u 到 v 选择走第一条路和选择走第二条路，虽然不是同一个物理过程，但在图论路径计数里，它们算两条不同的路径。所以重边引发的这次额外累加，恰好是题目要求统计的内容。

注意：如果题目明确说“重边只算一条路径”，那才需要去重。但洛谷 P1144 明确允许重边，并且按不同边计数，所以不要把重边去掉。

4.3 取模的位置：别等到最后

题目要求答案对 100003 取模，所以每一步累加都应该及时取模。不要写一个cnt[v] += cnt[u]，然后想着最后输出前再统一取模。如果图里存在很多条路径，cnt 的值可能早就超过 int 范围了，最后取模会得到错误的溢出结果。

我习惯的写法是：

cnt[v] = (cnt[v] + cnt[u]) % MOD;

在第一次赋值cnt[v] = cnt[u]时，cnt[u] 本身已经是取模后的值，所以继承下来的值也一定在合法范围内。这样整个计算过程里所有 cnt 都小于 100003，完全不用担心溢出。

4.4 用dist数组代替vis数组

很多初学 BFS 的人会额外开一个 bool vis 数组，标记节点是否已访问。在这道题里其实不需要，因为你已经有了 dist。dist 初始为 -1，就代表这个点还没有被计算过最短距离；当你第一次访问它时，dist 被赋成一个非负整数，以后再遇到就只需要判断是否等距。

这里有个容易犯迷糊的地方：如果某个节点已经被访问过，但此时又有一条边满足等距条件，说明它不是第一次被发现了，那么此时不应该再次入队，只累加 cnt 就够了。如果你画蛇添足地把它重新入队，会导致同一个点被处理多次，后面的节点计数也会跟着翻倍，最终答案完全不对。

4.5 输入与输出性能

这类百万级数据的题目，输入量动辄几百万个整数。我实测过，cin 如果不关闭同步，基本告别 AC；关闭同步后勉强能过，但耗时仍然偏高。scanf 是没问题的，getchar 手写快读更稳。所以我的 C++ 模板里直接写了快读函数。

输出也不要掉以轻心。需要输出 n 行整数，如果 n 是 1e6，用 printf 逐行打印是可以的，但要避免用 cout + endl，因为 endl 每次都会强制刷新缓冲区，在这种数据量下是致命打击。如果你喜欢用 cout，记得用'\n'代替 endl，并且提前关闭同步。

5. 从P1144延伸出去：带权最短路计数与DP题单的联动

5.1 带权图就用Dijkstra计数

如果把边权从 1 改成任意正整数，BFS 的“逐层扩展”性质就不成立了，因为更长的边可能先被访问到，但并不是最短路。这时候你需要换用堆优化 Dijkstra。

Dijkstra 里计数的核心逻辑其实和 BFS 版本几乎一样，只不过更新条件从dist[u] + 1变成了dist[u] + w：

if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; cnt[v] = cnt[u]; pq.push({dist[v], v}); } else if (dist[v] == dist[u] + w) { cnt[v] = (cnt[v] + cnt[u]) % MOD; }

Dijkstra 能保证每个节点第一次出队时，它的距离已经确定，之后不会再变小。所以当一个节点出队时，所有能贡献 cnt 的前驱也都已经处理完了，这时你再给它累加 cnt，就不会发生“前驱还没算好”的尴尬情况。正因为这个性质，Dijkstra 最短路计数是所有带权最短路计数问题的通用方案。

5.2 为什么说它是一道“披着图论外衣的DP”

把最短路计数抽象一下，你会发现它完全符合 DP 的三个要素：状态是每个点的 cnt，转移方程是cnt[v] += cnt[u]，顺序是 dist 递增。由于最短路的性质，所有点按照 dist 从小到大排成一个 DAG，不存在环，所以可以安全地做动态规划。

这就解释了为什么有些“洛谷动态规划题单”里会收录它。很多 DP 题难的地方在于你不知道转移顺序，而最短路计数里 BFS 帮你把顺序排好了，你只需要专心写转移逻辑。反过来想，以后再遇到“DAG 上路径计数”的题，你完全可以套用这套思维：先把图拓扑排序，再按拓扑序做状态转移。P1144 就是一个非常好的热身。

5.3 几个值得动手练的小变式

如果你刷完 P1144 还想再巩固一下，可以考虑下面几个方向：

把输出从“1 到每个点”改成“只输出 1 到 n 的最短路计数”，实现上几乎零改动，但能帮你确认自己有没有真正理解输出逻辑。把图改成有向图，输入时只加一条方向的边，重新跑一遍，感受一下有向和无向在 BFS 处理上的区别。再进阶一点，求出所有最短路经过的总边数，这就要额外记录每个点最短路的前驱数量，并做一次汇总 DP，是 P1144 的一个不错延伸。

这些变式都不会跑出太多新知识点，但对巩固思路非常有帮助。

我个人刷这题的体会是，代码其实很短，真正值钱的是那个 if 的判断顺序。第一次写的时候我习惯先判dist[to] == dist[u] + 1再判是否未访问，结果起点和重边样例直接挂掉。后来我每次写图论计数题都会默念：先更新未访问，再累加等距。这个顺序不是行文习惯，而是算法正确性的直接体现。如果你也卡在这题，不要急着看更多题解，把dist[u] + 1和cnt[v] += cnt[u]这两行想明白，比背十道模板都有用。