Skip to content

「POI2004」The competition

题解约 1.1 千字
# 图论 # POI # 最短路 # Dijkstra # 2004 # 二进制拆分
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

在 Byte 山的山脚下有一个洞穴入口。这个洞穴由复杂的洞室经过隧道连接构成。洞穴的入口是一条笔直通向「前面洞口」的道路。隧道互相都不交叉（他们只在洞室相遇）。两个洞室要么就通过隧道连接起来,要么就经过若干隧道间接的相连。

现在决定组织办一个「King’s of Byteotia Cup」比赛。参赛者的目标就是任意选择一条路径进入洞穴并尽快出来即可。一条路径必须经过除了「前面洞口」之外还至少要经过其他一个洞室。一条路径中一个洞不能重复经过(除了“前面洞室”以外),类似的一条隧道也不能重复经过。

一个著名的洞穴探险家 Byteala 正准备参加这个比赛。Byteala 已经训练了数月而且他已获得了洞穴系统的一套详细资料。对于每条隧道他都详细计算了从两个方向经过所需要的时间。经过一个洞室的时间很短可以忽略不记。现在 Byteala 向计算一条符合条件的最优路径。

#输入格式

第一行有两个数 nn 和 mm 分别表示洞室的数目以及连接他们的隧道的数目。洞室从 11 到 nn 编号。「前面洞室」的编号为 11。

接下来 mm 行描述了所有的隧道。每行四个整数 a,b,c,da, b, c, d 表示从洞室 aa 到洞室 bb 需要 cc 分钟的时间，而从洞室 bb 到洞室 aa 需要 dd 分钟的时间。你可以假设符合要求的路径肯定存在。

#输出格式

输出一行，表示最少需要多少时间完成比赛。

#样例输入输出

样例输入 #1

3 3
1 2 4 3
2 3 4 2
1 3 1 1

样例输出 #1

6

#数据范围与约定

对于 100%100\% 的数据，3≤n≤50003 \leq n \leq 5000，3≤m≤100003 \leq m \leq 10000，1≤a,b≤n1 \leq a, b \leq n，a≠ba \ne b，1≤c,d≤100001 \leq c, d \leq 10000。

#思路

求经过 11 号点的最短有向环路的长度。

一条有向环一定是这样的： 1→x→⋯→y→11 \to x \to \dots \to y \to 1。那么暴力就是枚举 x,yx, y 然后跑最短路。

但是这里的最短路是可以「并行」地求的。也就是说，如果给定两个不相交的点集 A,BA, B，那么我们可以用一次最短路的时间求出所有点对 (x,y)(x, y) 满足 x∈A,y∈Bx \in A, y \in B 的最短路的最小值。可以采用二进制拆分的方法实现。

#代码

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
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
96
97
98
99
100
#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int INF = 0x3f3f3f3f;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, ans = INF;

    cin >> n >> m;

    int s = 0, t = n + 1, size = t + 1;
    std::vector<std::tuple<int, int, int, int>> edges(m);

    for (auto& e : edges) {
        cin >> std::get<0>(e) >> std::get<1>(e) >> std::get<2>(e) >> std::get<3>(e);
    }

    for (int k = 0; k <= std::__lg(n); k++) {
        std::vector<std::vector<std::pair<int, int>>> g(size);

        for (auto& e : edges) {
            int u, v, a, b;

            std::tie(u, v, a, b) = e;

            if (u == 1) {
                if (v & (1 << k)) {
                    g[s].emplace_back(v, a);
                    g[v].emplace_back(s, b);
                } else {
                    g[v].emplace_back(t, b);
                    g[t].emplace_back(v, a);
                }
            } else if (v == 1) {
                if (u & (1 << k)) {
                    g[s].emplace_back(u, b);
                    g[u].emplace_back(s, a);
                } else {
                    g[u].emplace_back(t, a);
                    g[t].emplace_back(u, b);
                }
            } else {
                g[u].emplace_back(v, a);
                g[v].emplace_back(u, b);
            }
        }

        std::function<int(int, int)> dijkstra = [&](int s, int t) -> int {
            std::vector<int> dist(size, INF);
            std::vector<bool> vis(size);
            std::priority_queue<
                std::pair<int, int>,
                std::vector<std::pair<int, int>>,
                std::greater<>>
                q;

            q.emplace(0, s);
            dist[s] = 0;

            while (!q.empty()) {
                int u = q.top().second;
                q.pop();

                if (vis[u]) continue;
                vis[u] = true;

                for (auto e : g[u]) {
                    int v = e.first,
                        w = e.second;

                    if (dist[v] > dist[u] + w) {
                        dist[v] = dist[u] + w;

                        q.emplace(dist[v], v);
                    }
                }
            }

            return dist[t];
        };

        ans = std::min({ans, dijkstra(s, t), dijkstra(t, s)});
    }

    cout << ans << endl;

    return 0;
}