很好玩的题，自己推出来了。（虽然最后还是翻题解才发现自己哪里错了……）

这个贡献式子是二次的，而且还和 $u, v, p, q$ 至少四个参数相关，很吓人。
第一反应是考虑 DP 做这个事情，由于涉及点之间的转移，以及时间先后的问题，所以，设 $dp_{u, i}$ 表示在 $i$ 时刻到达 $u$ 点的最小烦躁值
假设有一条边 $u \to v$，出发时间 $p$ 到达时间 $q$，则不难写出如下方程：

$$dp_{v, q} \leftarrow dp_{u, i} + A(p-i)^2 + B(p-i) + C \quad \quad (i \leq p)$$

其实就是枚举 $i$ 时刻到达 $u$ 点，然后通过该线路转移到 $v$。
这个式子有两个问题：

1. 空间和时间都爆了。
2. 在求 $dp_{v,q}$ 的时候需要保证 $dp_{u,i}$ 都已经计算完。

这里我纠结了挺久的，以为只要保证 $\forall i, dp_{u}$ 被计算完成就行了，接着可以怎么动态开点优化一下空间，时间复杂度再说。
但事实是，这张图不一定是 DAG，不能拓扑排序。

那么不妨跳出来重新看问题，我们只需要保证 $\forall i \leq q, dp_{u,i}$ 被计算完。
所以显而易见地，可以按照 $q$（到站时刻）将所有线路排序，依次插入这些线路。
然后新的问题是，DP 是否有后效性？显然不会，就算有环再绕回来，它也只能影响后面的时刻这个点的 DP 信息。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, M = 4e3 + 5;
int n, m, A, B, C;
struct railway { int u, v, p, q; } edge[M];
inline bool cmp(railway a, railway b) { return a.q < b.q; }

long long dp[N][M];

int main() {
    memset(dp, 0x3f, sizeof dp), dp[1][0] = 0ll;
    scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
    for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &edge[i].u, &edge[i].v, &edge[i].p, &edge[i].q);
    sort(edge + 1, edge + 1 + m, cmp);
    long long res = 1e18;
    for (int t = 1; t <= m; t++) {
        auto [u, v, p, q] = edge[t];
        for (int i = 0; i <= p; i++) dp[v][q] = min(dp[v][q], dp[u][i] + A * 1ll * (p - i) * 1ll * (p - i) + B * 1ll * (p - i) + C);
        if (v == n) res = min(res, dp[v][q] + q);
    }
    printf("%lld\n", res);
    return 0;
}

接下来考虑先排序，然后在上述算法的基础上优化时空复杂度。
首先不需要真的开两维的 dp 数组，因为对于一个点 $v$ 有用的状态只有 $\forall (u \to v, p, q)$ 中的 $dp_{v, q}$。
因此动态开点（vector）存 DP 值即可。
然后是时间复杂度的问题。

看到平方贡献，想到拆式子 斜率优化。

$$\min \{ dp_{u, i} + A(p^2-2ip+i^2) + B(p-i) + C\}$$
$$\min \{ \color{green}{dp_{u, i}+Ai^2-Bi} \color{blue}{-2Ap} \color{red}{i} \} \color{purple}{+ Ap^2 + Bp + C}$$

于是得到 $k, x, y, c$，接下来推式子，设 $i_1 \lt i_2$，则有：

$$kx_1 + y_1 \leq kx_2 + y_2$$
$$2Ap \leq \frac{y_1 - y_2}{x_1 - x_2}$$

观察形式：取 $\min$ 维护下凸壳，$x$ 单调递增但 $k$ 不单调，所以用单调队列二分维护。
然后愉快地 WA 了洛谷 #9 #19 两个点。

之前的做法是按 $q$ 排序，每次把当前的 $u \to v$ 完成转移之后直接扔进 $v$ 的单调队列里面。
问题是，$p$ 的查询不具有单调性，所以如果之后有从 $v$ 出发的列车，最优决策可能会被刚刚扔进去的覆盖掉。
所以正确做法是：按照 $p$ 排序，每次把 $\leq p$ 的所有待加入 DP 值扔进对应点的单调队列，更新完当前节点 $v$ 的 DP 值之后也把它先存着，延后再加入。

由于红温了所以代码整得很丑……最初一版的代码其实还挺好看的。

#include <bits/stdc++.h>
#define PIL pair<int, long long>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5, T = 4e4 + 5;
const long long INF = 1e18;
int n, m, A, B, C;
struct railway { int u, v, p, q; } edge[M];
inline bool cmp(railway a, railway b) { return a.p < b.p; }

struct Queue {
    vector<PIL> q;
    int st, ed;
    inline void init() { q.clear(); st = 0, ed = -1; }
    inline void push(PIL x) { q.push_back({0, 0ll}), q[++ed] = x; }
} dp[N];  // 先 time 后 dp

#define Q dp[u]
#define P dp[v]

#define X(t) t.first
#define Y(t) (t.second + A*1ll*t.first*1ll*t.first - B*1ll*t.first)
inline double slope(PIL a, PIL b) {
    if (Y(a) == Y(b)) return 0.0;
    if (X(a) == X(b)) return (Y(a) < Y(b)) ? 1e18 : -1e18;
    return (Y(b) - Y(a)) * 1.00 / (X(b) - X(a));
}
inline bool check1(PIL a, PIL b, long long k) {
    // return slope(a, b) <= k;
    if (Y(a) == Y(b)) return 1;
    if (X(a) == X(b)) return 1;
    return Y(b) - Y(a) <= (__int128)k * (X(b) - X(a));
}
inline bool check2(PIL a, PIL b, PIL c, PIL d) {
    // return slope(a, b) >= slope(c, d);
    return (__int128)(Y(b) - Y(a)) * (X(d) - X(c)) >= (__int128)(Y(d) - Y(c)) * (X(b) - X(a));
}

vector< pair<int, PIL> > arr[T];

int main() {
    scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
    for (int i = 1; i <= n; i++) dp[i].init();
    for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &edge[i].u, &edge[i].v, &edge[i].p, &edge[i].q);
    sort(edge + 1, edge + 1 + m, cmp);
    long long res = INF;

    dp[1].push({0, 0ll});
    for (int i = 2; i <= n; i++) dp[i].push({0, INF});
    int Tid = 0;
    for (int t = 1; t <= m; t++) {
        while (Tid < edge[t].p) {    // 集体插入
            ++Tid;
            for (auto it : arr[Tid]) {
                // 转移，扔进 P 中
                int v = it.first; PIL now = it.second;
                while (P.st < P.ed && check2(P.q[P.ed - 1], P.q[P.ed], P.q[P.ed], now)) P.ed--;
                P.push(now);
            }
        }
        auto [u, v, p, q] = edge[t];
        // for (int i = 0; i <= p; i++) dp[v][q] = min(dp[v][q], dp[u][i] + A * 1ll * (p - i) * 1ll * (p - i) + B * 1ll * (p - i) + C);
        // 从 Q 中找最优决策点
        int l = Q.st, r = Q.ed;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if ( Q.q[mid].first <= p && check1(Q.q[mid - 1], Q.q[mid], 2ll * A * p) ) l = mid;
            else r = mid - 1;
        }
        auto [i, val] = Q.q[l];  // i -> time; val -> dp
        if (val == INF || i > p) continue;
        PIL now = {q, val + A * 1ll * (p - i) * 1ll * (p - i) + B * 1ll * (p - i) + C};
        arr[q].push_back({v, now});
        if (v == n) res = min(res, now.second + q);
    }
    printf("%lld\n", res);
    return 0;
}