洛谷P6302 [NOI2019] 回家路线 加强版 题解
题意：
喵喵国的铁路系统中有 \(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}\left(A(p_{s_{j+1}}-q_{s_j})^2+B(p_{s_{j+1}}-q_{s_j})+C\right) \] 小喵想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。
输入格式：
第一行五个整数 \(n, m, A, B,C\)，变量意义见题目描述。
接下来 \(m\) 行，第 \(i\) 行四个整数 \(x_i, y_i, p_i, q_i\)，分别表示 \(i\) 号列车的出发站、到达站、出发时刻与到达时刻。
输出格式：
输出仅一行一个整数，表示所求的答案。
数据范围：
对于所有的测试点，保证 \(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\)。
容易发现，除去其他零头，每条边的贡献就是一个二次函数，而且看上去就是个斜率优化。
这道题又有两个维度：时间&节点。好像没法全压到dp方程里去。（查看题解进行中）
于是我们考虑以边为基础dp。设 \(f_{i}\) 表示走 \(i\) 路径前的总花费，则 \[ f_i = f_j + A(p_i - q_j)^2 + B(p_i-q_j) + C \] 改一下形式 \[ f[j]+A q_j^2-B q_j=(2 A p_i )q_j+(f_i-A p_i^2-B p_i-C) \] 把边按 \(p\) 排个序，\(k\) 就单调不减了，可以斜率优化。
但是这道题还有一些限制条件，比如 \(y_j=x_i,q_j \le p_i\)
第一个可以通过维护 \(n\) 个单调队列，\(i\) 进队时就丢到 \(y_i\) 个里面，求 \(f_i\) 的时候把 \(x_i\) 拿出来用
第二个可以在我们算出 \(f_i\) 后不直接把它塞到对应的单调队列中，而是按 \(q\) 放入对应的栈中
并且对于每个相等的 \(p_i=t\) ，在算出 \(f_i\) 之前，把所有 \(q_j=t\) 放到单调队列中，则任意 \(q_j\le p_i\) 必有 \(p_j < p_i\)
时间复杂度 \(\mathcal{O(n+m)}\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define pf(x) ((x) * (x))
#define M ((int)(1e6 + 15))
vector<int> pos[M],ins[M],Q[M];
int n,m,A,B,C,T,res=INF,x[M],y[M],h[M],t[M],dp[M];
struct node{ int x,y,p,q; } a[M];
double slope(int i,int j)
{
int tx = x[j] - x[i], ty = y[j] - y[i];
if(!tx)
{
if(ty > 0) return INF;
return -INF;
}return (double)ty/tx;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m >> A >> B >> C;
for(int i = 1; i <= m; i++)
{
cin >> a[i].x >> a[i].y >> a[i].p >> a[i].q;
up(T, a[i].q); pos[a[i].p].push_back(i);
}
for(int i = 1; i <= n; i++) h[i] = 0, t[i] = -1;
for(int pi = 0; pi <= T; pi++)
{
for(int i : ins[pi])
{
int v = a[i].y;
while(h[v] < t[v] && slope(Q[v][t[v]-1], Q[v][t[v]]) >= slope(Q[v][t[v]-1], i)) t[v]--;
++t[v];
if(t[v] >= Q[v].size()) Q[v].push_back(i);
else Q[v][t[v]] = i;
}
for(int i : pos[pi])
{
int u = a[i].x; double k = 2.0 * A * pi;
while(h[u] < t[u] && slope(Q[u][h[u]], Q[u][h[u]+1]) < k) h[u]++;
if(h[u] > t[u] && u != 1) continue;
int j = (u == 1 && h[u] > t[u]) ? 0 : Q[u][h[u]];
dp[i] = dp[j] + A * pf(a[i].p - a[j].q) + B * (a[i].p - a[j].q) + C;
x[i] = a[i].q, y[i] = dp[i] + A * pf(a[i].q) - B * a[i].q;
ins[a[i].q].push_back(i);
if(a[i].y == n) down(res, dp[i] + a[i].q);
}
}
cout << res << '\n';
return 0;
}
