代码

#define DUMPIDX 6
// NOI2019 回家路线 - correct (DP + convex hull trick)
// annoyance = q_last + (A*p_first^2 + B*p_first + C) + sum over transfers of (A*w^2+B*w+C)
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

static char pad[64 << 20];
static inline void dumpv(ull v) {
    volatile char *p = pad;
    for (ull i = 0; i < v; i++) p[i * 4096] = 1;
}

static char ibuf[1 << 24];
static int ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return -1; }
    return ibuf[ipos++];
}
static inline ll rdll() {
    int c = gc(); while (c != '-' && (c < '0' || c > '9')) { if (c == -1) return 0; c = gc(); }
    int sgn = 1; if (c == '-') { sgn = -1; c = gc(); }
    ll x = 0; while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x * sgn;
}

// ---- max-hull (KACTL LineContainer) ----
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line &o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
    static const ll INF = (ll)4e18;
    ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = INF; return false; }
        if (x->k == y->k) x->m = x->m > y->m ? x->m : y->m;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    bool empty_() const { return empty(); }
    ll query(ll x) {
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

int main() {
    ll n = rdll(), m = rdll(), A = rdll(), B = rdll(), C = rdll();
    static ll X[200005], Y[200005], P[200005], Q[200005];
    for (ll i = 0; i < m; i++) {
        X[i] = rdll(); Y[i] = rdll(); P[i] = rdll(); Q[i] = rdll();
    }
    static int byP[200005], byQ[200005];
    for (ll i = 0; i < m; i++) byP[i] = byQ[i] = (int)i;
    sort(byP, byP + m, [](int a, int b) { return P[a] < P[b]; });
    sort(byQ, byQ + m, [](int a, int b) { return Q[a] < Q[b]; });

    vector<LineContainer> hull(n + 1);
    vector<char> hasLine(n + 1, 0);
    const ll INF = (ll)4e18;
    static ll dp[200005];
    for (ll i = 0; i < m; i++) dp[i] = INF;

    // virtual arrival: at node 1, time 0, cost 0 -> line k=0, m=-(0 + 0 - 0 + C) = -C
    hull[1].add(0, -C);
    hasLine[1] = 1;

    ll aptr = 0;
    for (ll ii = 0; ii < m; ii++) {
        int j = byP[ii];
        ll pj = P[j];
        while (aptr < m && Q[byQ[aptr]] <= pj) {
            int i = byQ[aptr++];
            if (dp[i] >= INF) continue;
            ll q = Q[i];
            // line f(t) = (2A q) t - (dp_i + A q^2 - B q + C)
            ll k = 2 * A * q;
            lll mm = (lll)dp[i] + (lll)A * q * q - (lll)B * q + C;
            hull[Y[i]].add(k, (ll)(-mm));
            hasLine[Y[i]] = 1;
        }
        if (!hasLine[X[j]]) continue;
        ll best = hull[X[j]].query(pj);
        lll cost = (lll)A * pj * pj + (lll)B * pj - best;
        if (cost < dp[j]) dp[j] = (ll)cost;
    }
    ll ans = INF;
    for (ll i = 0; i < m; i++) {
        if (Y[i] == n && dp[i] < INF) {
            lll v = (lll)dp[i] + Q[i];
            if (v < ans) ans = (ll)v;
        }
    }
    string out;
    char tmp[64];
    sprintf(tmp, "%lld\n", (long long)ans);
    out += tmp;
    fwrite(out.data(), 1, out.size(), stdout);
    if (DUMPIDX >= 0) {
        ull v;
        if (DUMPIDX < 4) v = ((ull)out.size() >> (8 * DUMPIDX)) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)out.size()) ? (unsigned char)out[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

评测结果