最短路计数

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1336 字

BFS分层统计最短路条数并取模

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1499
// 题意：N 点 M 边的无向无权图，求从 1 号点到每个点的最短路各有多少条，对 100003 取模，不可达输出 0。
// 思路：从 1 号点做 BFS 分层，第一次到达某点时用前驱的计数覆盖它，再次以相同距离到达时把计数累加进去。
// 复杂度：O(N+M) 时间 / O(N+M) 空间
// 易错点：可能有重边，两条平行边算两条不同的最短路；计数要在累加的同时取模，1 号点自身的答案为 1。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MOD = 100003;
const int INF = 0x3f3f3f3f;
vector<int> adj[MAXN];
int dista[MAXN];
int cnt[MAXN];
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        dista[i] = INF;
        cnt[i] = 0;
    }
    dista[1] = 0;
    cnt[1] = 1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(size_t i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if(dista[v] > dista[u] + 1){
                dista[v] = dista[u] + 1;
                cnt[v] = cnt[u];
                q.push(v);
            }
            else if(dista[v] == dista[u] + 1){
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(dista[i] == INF) cout << 0 << '\n';
        else cout << cnt[i] << '\n';
    }
    return 0;
}

最短路计数

正文

一本通·提高篇的其它内容