AT_abc319_g

· · 题解

题目大意：

给你一张 N 个节点的无向完全图，现在删了 M 条边，请问从 1 出发有多少条最短路径到达 N？

解题思路：

首先有一个可以过 N \le 5000 的做法，就是暴力 bfs，然后存储最短路径和方案数，向外扩张即可，O(n^2)。
但是怎么才能过呢？首先我们可以将问题简化一下，假设问 1 到 N 的最短路径长度。
不难想到可以按照 1 \to i 的最短路径长度分层。
那么可以设 cnt_{i} 表示上一层的点有多少不和 i 连边，最后如果队列空了，就枚举所有未遍历的点，判断一下 cnt_{i} 是否等于上一层点的个数，如果等于，说明现在它还不能被直接遍历，否则将它推进队列中。
那么同理，设 f_{i} 表示 1 \to i 有几条最短路径。然后再维护 g_{i} 表示在上一层不与 i 连边的点的 f_{i} 之和，最后算答案即可。
时间复杂度：
若 N \le 5000 则时间复杂度为 O(n^2 + m)。
若 5000 < N \le 2 \times 10^5 则时间复杂度为 O(n+m)。

代码：


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;

bool vis[200005];
int CNT, cnt[200005];
int n, m, f[200005], g[200005], sum;
vector<int> G[200005];
signed main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    vis[1] = f[1] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        sum += f[x], CNT++;

        for(auto y : G[x]){
            if(vis[y]) continue;
            g[y] += f[x];
            cnt[y]++;
        }

        if(q.empty()){
            for(int i = 1; i <= n; i++){
                if(!vis[i] && cnt[i] != CNT){
                    q.push(i);
                    f[i] = (sum % mod - g[i] % mod + mod) % mod;
                    vis[i] = 1;
                }
                g[i] = 0, cnt[i] = 0;
            }
            sum = 0, CNT = 0;
        }
    }
    if(!vis[n]) cout << -1 << endl;
    else cout << f[n] << endl;
    return 0;
}