DDOSvoid's Blog

2021 CCPC网络赛 I Public Transport System

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

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=7134

简要题意：给定一张 $n$ 个点 $m$ 条边的有向图，每条边有两种权值 $a_i,b_i$，对于一条路径，如果路径上的第 $i$ 条边的 $a$ 大于第 $i-1$ 条边的 $a$，那么第 $i$ 条边的权值为 $a-b$，否则为 $a$，求 $1$ 到其它所有点的最短路

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

Solution

注意到一条边的权值跟它上一条边有关系，我们考虑将边转换成点，然后对于原图中的一个中转点，我们考虑将其出边全部新建一个副本，副本与自身相连，然后排序一下串起来即可

考场上的写法有点冗余，点数为 $n+2m+1$，边数为 $6m$，另外需要注意一条边代表它指向的那个点

时间复杂度 $O(6m\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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>
#define maxn 500010
#define maxm 1200010
#define ll long long
#define INF 1000000000000000000
using namespace std;

struct Edge {
    int to, next, w; 
} e[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++;
}

int n, m, id[maxn];
struct node {
    int x, a, b;

    node(int x = 0, int a = 0, int b = 0) : x(x), a(a), b(b) {}
    friend bool operator < (const node &u, const node &v) { return u.a < v.a; }
}; vector<node> in[maxn], out[maxn];

struct Queue {
    int k; ll d;

    friend bool operator < (const Queue &u, const Queue &v) { return u.d > v.d; } 
}; bool vis[maxn]; ll dis[maxn]; int cnt;
priority_queue<Queue> Q; 
void dijkstra(int s) {
    fill(vis, vis + cnt, 0); 
    fill(dis, dis + cnt, INF); dis[s] = 0;
    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, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ v, dis[v] }); 
            }
        }
    }       
} 

ll ans[maxn];
void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) ans[i] = INF, in[i].clear(), out[i].clear(); ans[1] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y, u, v; cin >> x >> y >> u >> v; id[i] = y;
        in[y].emplace_back(i, u, v); out[x].emplace_back(i, u, v);
    } cnt = m + 1; fill(head + 1, head + n + 2 * m + 2, -1); c1 = 0; 
    for (int o = 1; o <= n; ++o) {
        if (!in[o].size() || !out[o].size()) continue;
        sort(in[o].begin(), in[o].end());
        sort(out[o].begin(), out[o].end());
        int l = cnt; cnt += out[o].size(); 
        for (int i = 0; i < out[o].size(); ++i) {
            if (i < out[o].size() - 1) add_edge(l + i, l + i + 1, 0);
            add_edge(l + i, out[o][i].x, out[o][i].a - out[o][i].b);
        } int j = 0;
        for (int i = 0; i < in[o].size(); ++i) {
            while (j < out[o].size() && out[o][j].a <= in[o][i].a) ++j;
            if (j < out[o].size()) add_edge(in[o][i].x, l + j, 0);
        }
        for (auto t : in[o]) add_edge(t.x, cnt, 0);
        for (auto t : out[o]) add_edge(cnt, t.x, t.a);
        ++cnt;
    }
    for (auto t : out[1]) add_edge(cnt, t.x, t.a);
    ++cnt; dijkstra(cnt - 1);
    for (int i = 1; i <= m; ++i) ans[id[i]] = min(ans[id[i]], dis[i]);
    for (int i = 1; i <= m; ++i) id[i] = 0;
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == INF) ans[i] = -1;
        cout << ans[i] << " \n"[i == n];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int T; cin >> T; 
    while (T--) work();
    return 0;
}