$$\color{Red}{最短路计数—论述最短路和拓扑结构的关系}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

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

输入格式

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

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

输出格式

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

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

数据范围

1 ≤ N ≤ 10 ^ 5

1 ≤ M ≤ 2 × 10 ^ 5

输入样例：

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

输出样例：

1
1
1
2
4

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

解析

由dp引申到最短路和拓扑图

首先计数问题，我们往往都是通过dp来解决。即我们要寻找递推状态，即每个点的最短路个数，应该是前面的点的最短路，加上边权，刚好等于终点的最短路。

那么我们就应该已知一个问题，我们能进行如上递推的两大前提 —> 1. 我们首先已知后继点的最短路 2. 我们已知前驱点的最短路，一定是不可被更新的状态，即锁定的状态。

那么这种状态很容易让我们想到一个图的结构，即拓扑图，这道题保证边权都为1，即即便有环，也只是使得最短路延长，故不影响答案。

这道题主要的是，通过一个计数的问题，深刻的论述证明最短路的几个算法，是否天然使得节点最终形成了拓扑图。

那么我们学的哪些算法是天然满足拓扑图？

bfs dijkstra：bfs每次会把邻层全部更新，且每个点只会入队出队一次，故必满足拓扑图。dijkstra每次出队都是最近点，且也通过st保证锁定绝不会再次更新，也必然满足。

但上面两个算法有负权边就无法使用，因为无法保证每个点更新其他点的时候已经满足当前点的距离不会再被更新的更短了

spfa bellman_ford：这两个算法，每个点或边都没有锁定情况，故每个点或边可以出队或入队无数次，故能保证负权边的最短路可以进行计算，故肯定无法满足拓扑图。

那么如果是出现负权边还需要进行拓扑图的结构生成怎么办？

可以先用spfa或bellman_ford将最短路先计算出来，然后再根据实际d[j] = d[t] + w[i]把点按照拓扑结构入队，即根据最短路主动构建拓扑结构。

java bfs最短路

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;


/**
 * @author Fanxy
 */
public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m, idx;
    static int N = 100010, M = 400010, mod = 100003;
    static int[] e = new int[M];
    static int[] h = new int[N];
    static int[] ne = new int[M];
    static int[] d = new int[N];
    static int[] cnt = new int[N];

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void bfs() {
        Arrays.fill(d, INF);
        d[1] = 0;
        cnt[1] = 1;
        LinkedList<Integer> q = new LinkedList<>();
        q.add(1);
        while (!q.isEmpty()) {
            int t = q.removeFirst();
            for (int i = h[t]; i != -1; i=ne[i]) {
                int j = e[i];
                if (d[j] > d[t] + 1){
                    d[j] = d[t] + 1;
                    q.add(j);
                    cnt[j] = cnt[t];
                } else if (d[j] == d[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % mod;
            }
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a, b);
            add(b, a);
        }
        bfs();
        for (int i = 1; i <= n; i++) System.out.println(cnt[i]);
    }
}