[NOI2019] 回家路线加强版

GitHub 跳转原题关系图返回列表

把每个站点上的换乘 DP 写成关于发车时刻 p 的直线最小值查询，再按时间扫描并为每个站维护单调队列凸包。

OJ: luogu

题目 ID: P6302

难度:省选/NOI-

标签:动态规划斜率优化凸包优化按时间扫描

日期: 2026-06-21 07:23

题意

有很多班列车，每班车固定：

在站点 x_i 的时刻 p_i 发车
在站点 y_i 的时刻 q_i 到站

小猫从时刻 0 开始待在 1 号站，目标是最终到 n 号站。

等待 t 个时刻的代价是：

A t^2 + B t + C

最后到达终点时，还要再加上最终到达时刻。

思路

先看最直接的暴力转移：

cpp

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#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 62);
const int MAXM = 5005;

struct Train {
    int x, y, p, q;
} tr[MAXM];

int n, m;
long long A, B, C;
long long dp[MAXM];

long long wait_cost(long long t) {
    return A * t * t + B * t + C;
}

bool cmp_train(const Train &lhs, const Train &rhs) {
    if (lhs.q != rhs.q) {
        return lhs.q < rhs.q;
    }
    if (lhs.p != rhs.p) {
        return lhs.p < rhs.p;
    }
    if (lhs.x != rhs.x) {
        return lhs.x < rhs.x;
    }
    return lhs.y < rhs.y;
}

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

    // brute.cpp：小数据暴力 DP。
    // 按到达时间排序，枚举所有能接上的前一班车。
    cin >> n >> m >> A >> B >> C;
    for (int i = 1; i <= m; i++) {
        cin >> tr[i].x >> tr[i].y >> tr[i].p >> tr[i].q;
    }

    sort(tr + 1, tr + m + 1, cmp_train);

    long long answer = INF;
    for (int i = 1; i <= m; i++) {
        dp[i] = INF;
        if (tr[i].x == 1) {
            dp[i] = min(dp[i], wait_cost(tr[i].p));
        }
        for (int j = 1; j < i; j++) {
            if (dp[j] >= INF / 2) {
                continue;
            }
            if (tr[j].y == tr[i].x && tr[j].q <= tr[i].p) {
                dp[i] = min(dp[i], dp[j] + wait_cost(tr[i].p - tr[j].q));
            }
        }
        if (tr[i].y == n) {
            answer = min(answer, dp[i] + tr[i].q);
        }
    }

    cout << answer << '\n';
    return 0;
}

设 dp[i] 表示最后乘坐第 i 班列车时的最小烦躁值。

如果列车 j 能接到列车 i，那么：

dp[i] = min(dp[j] + A(p_i-q_j)^2 + B(p_i-q_j) + C)

若它是第一班车，还要考虑：

dp[i] = A p_i^2 + B p_i + C

把转移展开：

dp[i] = A p_i^2 + B p_i + C + min(dp[j] + A q_j^2 - B q_j - 2A q_j p_i)

对于固定的前驱 j，后半部分是关于 p_i 的一次函数。

所以可以对每个站点维护一个凸包：

一条线对应一种“已经到达这个站”的方案
之后若有列车从这个站发车，只要在 p_i 处查询最小值

又因为：

查询时间 p_i 按扫描顺序单调不减
插入时间 q_j 也单调不减，所以斜率单调

于是每个站点都可以用单调队列维护下凸壳。

主流程按时间从小到大扫描：

先处理当前时刻到达的列车，把它们对应的直线插入终点站
再处理当前时刻出发的列车，在起点站的凸壳上查询

这样自然支持 q_j = p_i 的零等待换乘。

DP 转移方程

核心状态：

dp[i] 为最后乘第 i 班车的最小烦躁值

核心转移：

dp[i]=A p_i^2+B p_i+C+min(dp[j]+Aq_j^2-Bq_j-2Aq_j p_i)

答案收束：

到终点列车 dp[i]+q_i 取最小

代码

cpp

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 62);
const int MAXN = 100005;
const int MAXM = 1000005;

struct Train {
    int x, y, p, q;
} tr[MAXM];

struct Line {
    long long k, b;
};

int n, m;
long long A, B, C;
long long dp[MAXM];
vector<int> depart_at[40005];
vector<int> arrive_at[40005];

// 每个站维护一个下凸壳，表示已经到达该站的所有方案。
struct Hull {
    vector<Line> q;
    int head = 0;

    void clear() {
        q.clear();
        head = 0;
    }

    bool empty() const {
        return head >= (int) q.size();
    }

    long long value(const Line &line, long long x) const {
        return line.k * x + line.b;
    }

    // 下凸壳判劣。
    bool bad(const Line &a, const Line &b, const Line &c) const {
        __int128 left = (__int128) (b.b - a.b) * (b.k - c.k);
        __int128 right = (__int128) (c.b - b.b) * (a.k - b.k);
        return left >= right;
    }

    void add_line(long long k, long long b) {
        Line line;
        line.k = k;
        line.b = b;
        if (!q.empty() && q.back().k == line.k) {
            if (q.back().b <= line.b) {
                return;
            }
            q.pop_back();
            if (head > (int) q.size()) {
                head = (int) q.size();
            }
        }
        while ((int) q.size() - head >= 2 && bad(q[(int) q.size() - 2], q[(int) q.size() - 1], line)) {
            q.pop_back();
        }
        q.push_back(line);
    }

    long long query(long long x) {
        while ((int) q.size() - head >= 2 && value(q[head], x) >= value(q[head + 1], x)) {
            head++;
        }
        return value(q[head], x);
    }
};

Hull station_hull[MAXN];

long long wait_cost(long long t) {
    return A * t * t + B * t + C;
}

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

    cin >> n >> m >> A >> B >> C;
    for (int i = 1; i <= m; i++) {
        cin >> tr[i].x >> tr[i].y >> tr[i].p >> tr[i].q;
        depart_at[tr[i].p].push_back(i);
        arrive_at[tr[i].q].push_back(i);
    }

    // 起点站 1 在时刻 0 就已经可以开始等待。
    // 若下一班车在时刻 p 发车，那么代价就是：
    // A p^2 + B p + C
    station_hull[1].add_line(-2LL * A * 0, 0);

    long long answer = INF;

    for (int t = 0; t <= 40000; t++) {
        // 先处理这个时刻到达的列车，因为 q_u <= p_v，允许到站后立刻换乘同一时刻发车的车。
        for (unsigned int idx = 0; idx < arrive_at[t].size(); idx++) {
            int id = arrive_at[t][idx];
            if (dp[id] >= INF / 2) {
                continue;
            }
            int y = tr[id].y;
            int q = tr[id].q;

            // 若之后在时刻 p >= q 从这个站继续走，
            // 新增等待代价是 A(p-q)^2 + B(p-q) + C。
            // 展开后关于 p 的部分为：
            // A p^2 + B p + C + (-2Aq) * p + (dp + Aq^2 - Bq)
            // 所以插入一条斜率 -2Aq 的直线。
            long long k = -2LL * A * q;
            long long b = dp[id] + A * 1LL * q * q - B * 1LL * q;
            station_hull[y].add_line(k, b);
        }

        for (unsigned int idx = 0; idx < depart_at[t].size(); idx++) {
            int id = depart_at[t][idx];
            int x = tr[id].x;
            int p = tr[id].p;

            dp[id] = INF;
            if (station_hull[x].empty()) {
                continue;
            }

            long long best = station_hull[x].query(p);
            dp[id] = A * 1LL * p * p + B * 1LL * p + C + best;

            if (tr[id].y == n) {
                answer = min(answer, dp[id] + tr[id].q);
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

时间复杂度 $O(m)$ ，空间复杂度 $O(m + n)$ 。

总结

这题看起来是图上最短路，实际上更像“按站点分组的 DP”。

关键是把等待代价展开成：

当前列车固定的二次项
前驱列车形成的直线项

这样才能把枚举前驱优化成凸包查询。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P6302 [NOI2019] 回家路线加强版

题目背景

本题是 NOI 2019 回家路线的加强版，除数据范围外均与原题相同。

题目描述

猫国的铁路系统中有 $n$ 个站点，从 $1 - n$ 编号。小猫准备从 $1$ 号站点出发，乘坐列车回到猫窝所在的 $n$ 号站点。它查询了能够乘坐的列车，这些列车共 $m$ 班，从 $1 - m$ 编号。小猫将在 $0$ 时刻到达 $1$ 号站点。对于 $i$ 号列车，它将在时刻 $p_i$ 从站点 $x_i$ 出发，在时刻 $q_i$ 直达站点 $y_i$ ，小猫只能在时刻 $p_i$ 上 $i$ 号列车，也只能在时刻 $q_i$ 下 $i$ 号列车。小猫可以通过多次换乘到达 $n$ 号站点。一次换乘是指对于两班列车，假设分别为 $u$ 号与 $v$ 号列车，若 $y_u = x_v$ 并且 $q_u \leq p_v$ ，那么小猫可以乘坐完 $u$ 号列车后在 $y_u$ 号站点等待 $p_v - q_u$ 个时刻，并在时刻 $p_v$ 乘坐 $v$ 号列车。

小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。

小猫在站点等待时将增加烦躁值，对于一次 $t (t \geq 0)$ 个时刻的等待，烦躁值将增加 $At^2 + Bt + C$ ，其中 $A, B,C$ 是给定的常数。注意：小猫登上第一班列车前，即从 $0$ 时刻起停留在 $1$ 号站点的那些时刻也算作一次等待。
若小猫最终在时刻 $z$ 到达 $n$ 号站点，则烦躁值将再增加 $z$ 。

形式化地说，若小猫共乘坐了 $k$ 班列车，依次乘坐的列车编号可用序列 $s_1, s_2, \cdots , s_k$ 表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件：

$x_{s1} = 1,y_{sk} = n$
对于所有 $j (1 \leq j < k)$ ，满足 $y_{sj} = x_{s_{j+1}}$ 且 $q_{sj}\leq p_{s_{j+1}}$

对于该回家路线，小猫得到的烦躁值将为：

q_{s_k}+(A\times p_{s_1}^2+B\times p_{s_1}+C)+\sum_{j=1}^{k-1}(A(p_{s_{j+1}}-q_{s_j})^2+B(p_{s_{j+1}}-q_{s_j})+C)

小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最小的烦躁值。题目保证至少存在一条可行的回家路线。

输入格式

第一行五个整数 $n, m, A, B,C$ ，变量意义见题目描述。

接下来 $m$ 行，第 $i$ 行四个整数 $x_i, y_i, p_i, q_i$ ，分别表示 $i$ 号列车的出发站、到达站、出发时刻与到达时刻。

输出格式

输出仅一行一个整数，表示所求的答案。

输入输出样例 #1

输入 #1

text

1
2
3
4
53 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

对于所有的测试点，保证 $2\le n\le 10^5$ ， $1\le m\le 10^6$ ，$0\le A\le 10$， $0\le B,C\le 10^7$ ， $1\le x_i,y_i\le n$ ， $x_i\neq y_i$ ， $0\le p_i<q_i\le 4\times 10^4$ 。

[NOI2019] 回家路线 加强版

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析

[NOI2019] 回家路线加强版