洛谷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}}$
对于该回家路线，小喵得到的烦躁值将为：
小喵想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。
输入格式：
第一行五个整数 $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$ 路径前的总花费，则
改一下形式
把边按 $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;
}
