【题解】HackerRank - Minimum Penalty Path

Posted on Edited on In Disqus:

题目

https://www.hackerrank.com/challenges/beautiful-path/problem

题意

求起点到终点的一条路径，使得边权 or 最小。

题解

官方题解

  • dp[u][k] 表示到结点 u 的代价为 k 的方案是否存在，然后在图上转移（dfs 一下就好了）。
  • 复杂度 \(O(n C)\)

题解

  • 复杂度更低，更省空间。
  • 从高到低考虑答案中的每一个 bit，如果没有这一位，则所有该 bit 为 1 的边都不能走，如果剩下的边无法使起点和终点联通，那么答案中的这一位只能为 1。
  • 如果确定了答案中的某一位必须为 1，那么所有边权就不需要考虑这一位了。
  • 从大到小计算出答案的每一位，连通性用并查集处理。
  • 复杂度 \(O(n \log C)\)

代码

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
#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 = 1E4 + 100;
struct E {
    int u, v;
    LL d;
};
vector<E> edges;
int n, m, fa[maxn], st, ed;

int findset(int x) { return fa[x] == -1 ? x : fa[x] = findset(fa[x]); }
void join(int u, int v) {
    int fu = findset(u), fv = findset(v);
    if (fu != fv) fa[fu] = fv;
}

int main() {
    memset(fa, -1, sizeof fa);
    cin >> n >> m;
    FOR (_, 0, m) {
        int u, v; LL d;
        scanf("%d%d%lld", &u, &v, &d);
        edges.push_back({u, v, d});
        join(u, v);
    }
    cin >> st >> ed;
    if (findset(st) != findset(ed)) {
        puts("-1");
        return 0;
    }
    LL ans = (1LL << 62) - 1;
    FORD (i, 61, -1) {
        ans ^= 1LL << i;
        memset(fa, -1, sizeof fa);
        for (E& e: edges)
            if ((e.d & ~ans) == 0)
                join(e.u, e.v);
        if (findset(st) != findset(ed)) ans ^= 1LL << i;
    }
    cout << ans << endl;
}