DDOSvoid's Blog

Luogu P3547 [POI2013]CEN-Price List

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

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $a$，现在将原图中所有最短路为 $2a$ 的点对 $(i,j)$ 之间加一条长度为 $b$ 的无向边，求新图的以 $S$ 为起点的单源最短路径

$n,m\le 10^5$

Solution

注意到只有三元环是没法享受到 $b$ 的路径，而三元环只有 $O(m\sqrt m)$ 个，所以我们直接在 $dijkstra$ 的过程中对于每个中转点维护现在还没有被更新的点集，初始时这个就是与这个点相邻的点，每次会留下与 $(u,v)$ 组成三元环的 $w$，这一部分的更新总时间复杂度就是 $O(m\sqrt m)$

总时间复杂度 $O(m\sqrt m+m\log m)$

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
77
78
79
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <array>
#include <map>
#define maxn 100010
#define INF 1000000000
#define ll long long
using namespace std;

int n, m, S, a, b, u[maxn], v[maxn], du[maxn];
vector<int> G[maxn];

map<array<int, 3>, int> mp;

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

struct Queue {
    int k, d;

    friend bool operator < (const Queue &u, const Queue &v) { return u.d > v.d; } 
}; int vis[maxn]; int dis[maxn]; 
void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    for (int i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0;
    priority_queue<Queue> Q; Q.push({ s, 0 });
    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; vector<int> tmp;
            for (auto w : G[v]) {
                array<int, 3> a = { u, v, w }; sort(a.begin(), a.end());
                if (mp.count(a)) tmp.push_back(w);
                else if (dis[w] > dis[u] + b) dis[w] = dis[u] + b, Q.push({ w, dis[w] });
            } swap(G[v], tmp);
            if (dis[v] > dis[u] + a) {
                dis[v] = dis[u] + a;
                Q.push({ v, dis[v] }); 
            }
        }
    }       
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> S >> a >> b;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        u[i] = x, v[i] = y; ++du[x], ++du[y];
        add_edge(x, y), add_edge(y, x);
    }
    for (int i = 1; i <= m; ++i) {
        if (du[u[i]] > du[v[i]] || du[u[i]] == du[v[i]] && u[i] > v[i]) swap(u[i], v[i]);
        G[u[i]].push_back(v[i]); 
    }
    for (int u = 1; u <= n; ++u) {
        for (auto v : G[u]) vis[v] = u; 
        for (auto v : G[u]) 
            for (auto w : G[v])
                if (vis[w] == u) {
                    array<int, 3> a = { u, v, w }; sort(a.begin(), a.end());
                    mp[a] = 1; 
                }
    }
    for (int i = 1; i <= n; ++i) G[i].clear();
    for (int i = 1; i <= m; ++i) G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
    dijkstra(S);
    for (int i = 1; i <= n; ++i) cout << dis[i] << "\n";
    return 0;
}