DDOSvoid's Blog

Luogu P4366 [Code+#4]最短路

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4366

简要题意：给定一个有 $n$ 个点的完全图，无向边 $$ 的权值为 $(u~xor~v)\times C$，$C$ 是给定的常数，现再给定 $m$ 条单向边 $(u,v,w)$ 和起点 $s$ 以及终点 $t$，求 $s$ 到 $t$​ 的最短路

$n\le 10^5,m\le 5\times 10^5$

Solution

我们对于特殊的边按位考虑，也就是把边拆开

对于点 $u$，向 $u~xor~2^i$ 连边，边权为 $C\cdot2^i$​

然后跑最短路即可

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>
#define maxn 100010
#define maxm 500010
#define ll long long
#define gc getchar
#define cQ const Queue
#define INF 1000000000000000000ll
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
} 

int n, m, C;

struct Edge {
    int to, next, w;
} e[maxn * 20 + maxm]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

struct Queue {
    int k; ll v;

    Queue() {}
    Queue(int _k, ll _v) { k = _k; v = _v; }

    friend bool operator < (cQ &u, cQ &v) { return u.v > v.v; } 
} ; priority_queue<Queue> Q;

bool vis[maxn]; int s, t; ll dis[maxn]; 
void dijkstra() {
    for (int i = 0; i <= n; ++i) dis[i] = INF; dis[s] = 0; 
    Q.push(Queue(s, dis[s]));
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push(Queue(v, dis[v]));
            }
        }
    }
} 

int main() { memset(head, -1, sizeof head); 
    n = read(); m = read(); C = read();
    for (int i = 1; i <= m; ++i) {
        int x = read(), y = read(), z = read();
        add_edge(x, y, z); 
    } s = read(); t = read(); 
    for (int u = 0; u <= n; ++u)
        for (int i = 0; i < 20; ++i) {
            int v = u ^ 1 << i; if (v > n) continue ;
            add_edge(u, v, (1 << i) * C); 
        }
    dijkstra(); cout << dis[t] << endl; 
    return 0;
}