最短路计数问题

Acwing 算法提高课 单源最短路扩展——最短路计数

在研究这个问题前我们可以回忆一下,在dp问题中我们是如何去统计方案数的 当我们通过状态i更新状态j,若相等则累加,若更新则使cnt[j] = cnt[i]

那么最短路问题是否能直接沿用这种方式来求方案数呢 ?
这个时候我们需要考虑清楚dp的本质,才能解释什么样的情况下可以通过这种方式来求得方案数
动态规划用已知状态来更新未知状态,换句话说,我们已经求过的__前驱状态__不会被反复更新
倘若我们把每一个状态看作一个点, 那么我们求每个状态的这个过程一定是满足__拓扑序__的

而这就是最短路问题中我们要求方案数的关键所在:
我们考虑这些最短路算法是否满足这一性质
1. BFS : 每个点只会出队一次,出队时保证最短路已经确定,不会再被其它点更新, 满足拓扑序 2. Dijkstra(双端队列bfs) : 弹出队列时已确保是最小值, 不会再被更新, 满足拓扑序 3. SPFA : 出队时会被再次更新, 不适宜直接求方案数事实上, 我们也可以绕两个弯借助最短路树求出方案数

本题(Acwing最短路计数)相对简单,使用bfs即可

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10, M = 4e5 + 10, P = 1e5 + 3;

int h[N], e[M], ne[M], idx;
int dist[N], cnt[N], n, m;
bool st[N];

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

void bfs(){
    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();
        
        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];
            }
            else if(dist[j] == dist[t] + 1)cnt[j] = (cnt[j] + cnt[t] ) % P;
            if(!st[j]){
                q.push(j);
                st[j] = true;
            }
        }
    }
}

int main(){
    freopen("cnt.in", "r", stdin);
    freopen("cnt.out", "w", stdout);
    
    memset(h, -1, sizeof h);
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    
    bfs();
    
    for(int i = 1; i <= n; i ++)
        printf("%d\n", cnt[i]);
    
    return 0;
}