Atcoder-abc254_e 题解

发表于2023-12-05更新于2023-12-29

题目传送门

一道暴力题……

度数和 kk 那么小？直接暴力 nn 遍 bfs，注意 bfs 的队列只能 push 距离不超过 33 的点。但有个问题，每次 bfs 都需要清空一次距离数组，这样子的时间复杂度是 O(n2)O(n^2) 的。但也不难想到，距离数组中被赋值的地方不会很多，记录一下就行。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;
const long long MOD = 998244353;

using ll = long long;
using i128 = __int128;
using ld = long double;
using f128 = __float128;

namespace xvl_ { 
    #define SP(n, x) std :: setprecision(n) << std :: fixed << x
    #define REP(i, l, r) for (auto i = (l); i <= (r); i++)
    #define PER(i, r, l) for (auto i = (r); i >= (l); i--)
    #define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
    #define SZ(x) (x.size())
    #define fst first
    #define snd second
    template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
    template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
struct Node { ll id, cnt; };
ll n, m, q;
ll dis[150005];
vector <int> G[150005];
vector <pair <int, int>> D[150005];
// first 代表编号，second 代表步数
void bfs(ll s) {
    if (s == 1) fill(dis + 1, dis + 1 + n, IMX);
    else for (auto v : D[s - 1]) dis[v.fst] = IMX;
    queue <Node> q;
    vector <int> p;
    q.push({s, 0}), dis[s] = 0;
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        for (auto v : G[cur.id]) {
            if (cur.cnt + 1 < dis[v] and cur.cnt + 1 <= 3) {
                dis[v] = cur.cnt + 1;
                p.push_back(v);
                q.push({v, dis[v]});
            }
        }
    }
    D[s].push_back(make_pair(s, 0));
    for (auto v : p) {
        if (dis[v] <= 3) D[s].push_back(make_pair(v, dis[v]));
    }
}
int main() {
    // freopen("InName.in", "r", stdin);
    // freopen("OutName.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    REP(i, 1, m) {
        ll u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    REP(i, 1, n) bfs(i);
    cin >> q;
    while (q--) {
        ll x, k, ans = 0;
        cin >> x >> k;
        for (auto v : D[x]) {
            if (v.snd <= k) ans += v.fst;
        }
        cout << ans << '\n';
    }
    return 0;
}