[Daimayuan] 最短路计数（C++，DP，图论）

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图。

问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第 $1$ 行包含两个正整数 $N$，$M$。

接下来 $M$ 行，每行两个正整数 $x,y$表示存在一条由顶点 $x$ 到顶点 $y$ 的边。（可能存在重边和自环）

输出格式

输出 $N$ 行，每行一个非负整数。

第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 的不同最短路个数。

由于数据可能很大，你只需要输出 $ansmod100003$ 的结果。

若顶点 $1$ 不能到达顶点 $i$，请输出 $0$。

样例输入

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例输出

1
1
1
2
4

数据范围

1 ≤ N ≤ 1 0 6 1≤N≤10^6 1≤N≤106， 1 ≤ M ≤ 2 × 1 0 6 1≤M≤2×10^6 1≤M≤2×106

提示

由于数据量较大，请使用较为快速的输入/输出方式。

解题思路

根据数据范围，我们估计算法的复杂度至多是$O(N)$，因此想到了动态规划：

对于节点$i$，有若干个节点与之相连，在与之相连的节点当中从$1$到 k 1 , k 2 , . . . , k n k_1,k_2,...,k_n k1​,k2​,...,kn​节点的路径长度相同且最短，那么我们计算得出，从$1$到节点$i$的最短路径数为 n u m [ k 1 ] + n u m [ k 2 ] + . . . + n u m [ k n ] num[k_1]+num[k_2]+...+num[k_n] num[k1​]+num[k2​]+...+num[kn​]。

以上是思路的主体部分，接下来实现代码：

数据量庞大，同时也是因为存在重边，故不能采用二维数组存图，因此采用链式前向星。

对于代码主体部分，维护一个队列与一个路径长度的数组。

初始化将$1$节点加入队列，然后不断尝试到达新的节点。

void solve() {q.push(1);while (!q.empty()) {int node = q.front(); q.pop();for (int i = head[node]; i != -1; i = edges[i].next) {int v = edges[i].v;q.push(v);}}
}

利用队列元素先进先出的特点，我们可以保证，队首的节点永远是距离$1$最近的节点。

进而我们可以保证，用队首去更新路径长度，得到的一定是最短路径长度。

void solve() {q.push(1);path[1] = 0;while (!q.empty()) {int node = q.front(); q.pop();int path_len = path[node] + 1;for (int i = head[node]; i != -1; i = edges[i].next) {int v = edges[i].v;if (path_len > path[v]) continue;if (path[v] == NaN) {//NaN代表无穷大，即为未到达的节点path[v] = path_len;q.push(v);}}}
}

以此为基础，很容易实现最初的思想：

void solve() {q.push(1);path[1] = 0;sum[1] = 1LL;while (!q.empty()) {int node = q.front(); q.pop();int path_len = path[node] + 1;for (int i = head[node]; i != -1; i = edges[i].next) {int v = edges[i].v;if (path_len > path[v]) continue;sum[v] = (sum[v] + sum[node]) % mod_num;if (path[v] == NaN) {path[v] = path_len;q.push(v);}}}
}

最后，AC代码如下：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <string.h>
using namespace std;
const int max_n = 1e6;
const int max_m = 2e6;
const int NaN = 0x3F3F3F3F;
const long long mod_num = 100003;struct edge { int v, next; }edges[2 * max_m];
int tot = -1, head[max_n + 1], path[max_n + 1];
queue<int>q;
long long sum[max_n + 1];void add_edge(int u, int v) {edges[++tot] = { v, head[u] }; head[u] = tot;edges[++tot] = { u, head[v] }; head[v] = tot;
}void solve() {q.push(1);path[1] = 0;sum[1] = 1LL;while (!q.empty()) {int node = q.front(); q.pop();int path_len = path[node] + 1;for (int i = head[node]; i != -1; i = edges[i].next) {int v = edges[i].v;if (path_len > path[v]) continue;sum[v] = (sum[v] + sum[node]) % mod_num;if (path[v] == NaN) {path[v] = path_len;q.push(v);}}}
}int main() {memset(head, -1, sizeof(int) * (max_n + 1));memset(path, 0x3F, sizeof(int) * (max_n + 1));int n, m;scanf("%d%d", &n, &m);//cin >> n >> m;int u, v;for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);//cin >> u >> v;add_edge(u, v);}solve();for (int i = 1; i <= n; i++) {printf("%lld\\n", sum[i]);}return 0;
}