【题解】HackerRank - Rust & Murderer

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/rust-murderer/problem

题意

求一个简单无向图的单源最短路（没有边权），但是题目给出的是该图的补图（也就是说，该图是在完全图的基础上去掉若干条边的结果）。

题解

  • 如果求出原图的话，显然因为边数太多，存都存不下。
  • 发现两点之间的最短距离的最大值不会太大（想一想完全图）。
  • 那么只要 bfs 即可，下面代码中的 bfs 写成了按层搜索的。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (false)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 2E5 + 100;
int T, n, m, st;
vector<int> G[maxn];
int d[maxn], cnt[maxn];

int main() {
    cin >> T;
    while (T--) {
        scanf("%d%d", &n, &m);
        FOR (i, 1, n + 1) G[i].clear();
        FOR (_, 0, m) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        cin >> st;
        vector<int> q;
        memset(d, -1, sizeof d);
        q.push_back(st); d[st] = 0;
        int dist = 1;
        while (!q.empty()) {
            memset(cnt, 0, sizeof cnt);
            int C = q.size();
            for (int u: q)
                for (int v: G[u])
                    ++cnt[v];
            q.clear();
            FOR (i, 1, n + 1)
                 if (d[i] == -1 && cnt[i] != C) {
                     d[i] = dist;
                     q.push_back(i);
                 }
            ++dist;
        }
        FOR (i, 1, n + 1)
            if (i != st) printf("%d ", d[i]);
        puts("");
    }
}