代码

#include <bits/stdc++.h>
#define N 200010
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

template <class Int> inline void read(Int& x) {
    x = 0; char ch = getchar(); int f = 1;
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    x *= f;
}

struct train {
    int x, y, p, q;
    bool operator<(const train& rhs) const { return (x < rhs.x) || (x == rhs.x && p < rhs.p); }
} t[N];

struct subway {
    int y, p, q;
    subway() {}
    subway(int y, int p, int q) : y(y), p(p), q(q) {}
};

struct arrival {
    int u;
    ll d, q;
    arrival() {}
    arrival(int u, ll d, ll q) : u(u), d(d), q(q) {}
};

int n, m;
ll A, B, C;
vector<subway> sub[N];
vector<arrival> f;

inline ll calc(ll x) { return A * x * x + B * x + C; }

int main() {
    read(n), read(m), read(A), read(B), read(C);
    for (int i = 1; i <= m; ++i) {
        read(t[i].x), read(t[i].y), read(t[i].p), read(t[i].q);
    }
    sort(t + 1, t + m + 1);
    for (int i = 1; i <= m; ++i) sub[t[i].x].push_back(subway(t[i].y, t[i].p, t[i].q));
    queue<arrival> q;
    q.push(arrival(1, 0, 0));
    while (!q.empty()) {
        arrival a = q.front(); q.pop();
        for (int i = 0; i < sub[a.u].size(); ++i) {
            subway tr = sub[a.u][i];
            if (a.q > tr.p) continue;
            arrival nxt(tr.y, a.d + calc(tr.p - a.q), tr.q);
            f.push_back(nxt);
            q.push(nxt);
        }
    }
    ll ret = 1e18;
    for (int i = 0; i < f.size(); ++i) {
        if (f[i].u == n) ret = min(ret, f[i].d + f[i].q);
    }
    printf("%lld\n", ret);
    return 0;
}

评测结果