<—点个赞吧QwQ

宣传一下算法提高课整理

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1$ 到 $N$。

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

输入格式

第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。

接下来 $M$ 行，每行两个正整数 $x,y$，表示有一条顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

输出 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出对 $100003$ 取模后的结果即可。

如果无法到达顶点 $i$ 则输出 $0$。

数据范围

$1 \\le N \\le 10^5$,
$1 \\le M \\le 2 \\times 10^5$

输入样例：

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

输出样例：

1
1
1
2
4

思路

设$cnt_i$表示$1\sim i$的最短路数量
对于每次$\text{SPFA}$的松弛操作中的每条边$(a,b,w)$，我们分类讨论：

1. 若$dist_b>dist_a+w$，则$cnt_b$应更新为$cnt_a$，因为以前的$cnt_b$不是最短路了。
2. 若$dist_b=dist_a+w$，则$cnt_b$应加上$cnt_a$，因为这里的最短路长度相同

代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010,M = 400010,MOD = 100003;
int n,m;
int h[N],e[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];
void add (int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void spfa () {
    queue <int> q;
    q.push (1);
    memset (dist,0x3f,sizeof (dist));
    dist[1] = 0;
    cnt[1] = 1;
    st[1] = true;
    while (q.size ()) {
        int t = q.front ();
        q.pop ();
        st[t] = false;
        for (int i = h[t];~i;i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + 1) {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                if (!st[j]) {
                    q.push (j);
                    st[j] = true;
                }
            }
            else if (dist[j] == dist[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % MOD;
        }
    }
}
int main () {
    memset (h,-1,sizeof (h));
    cin >> n >> m;
    while (m--) {
        int a,b;
        cin >> a >> b;
        add (a,b),add (b,a);
    }
    spfa ();
    for (int i = 1;i <= n;i++) cout << cnt[i] << endl;
    return 0;
}