代码

/*
 * Author       : YangDavid
 * Created Time : 2019年07月16日 星期二 08时42分36秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
//#define gc() getchar()

template<typename T> void read(T &x){
    x = 0; int f = 1; char ch = gc();
    while(!isdigit(ch) ) { if(ch == '-') f = -1; ch = gc();}
    while( isdigit(ch) ) {x = x * 10 + ch - 48; ch = gc();}
    x *= f;
}
template<typename T> void write(T x) {
    if(x < 0) putchar('-'), write(-x);
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

const int maxn = 444444;
struct edge {
    int from, to, p, q;
    edge(int f=0, int t=0, int P=0, int Q=0):
        from(f), to(t), p(P), q(Q) { }
    bool operator < (const edge& rhs) const { return p > rhs.p; }
} e[maxn], eeee[maxn];

ll n, m, A, B, C;
int head[maxn], nxt[maxn], ecnt, cur[maxn];
ll g(ll T) { return T * T * A + T * B + C; }
vector<pair<int, long long> > upd[1020];
bitset<100020> bs;
ll dp[maxn];

void addedge(const edge& ed) {
    e[++ecnt] = ed;
    nxt[ecnt] = head[ed.from];
    head[ed.from] = ecnt;
}
inline void up(ll &x, ll y) { x = min(x, y); }
ll ans = 0x3f3f3f3f3f3f3f3f;

signed main() {
    freopen("route.in", "r", stdin);
    freopen("route.out", "w", stdout);
    int x, y, p, q, mxp = 0;
    read(n), read(m), read(A), read(B), read(C);
    rep(i, m) {
        read(x), read(y), read(p), read(q);
        eeee[i] = edge(x, y, p, q);
        mxp = max(mxp, eeee[i].p);
    }
    sort(eeee + 1, eeee + 1 + m);
    rep(i, m) { 
        addedge(eeee[i]);
    }
    rep(i, n) cur[i] = head[i];

    upd[0].push_back(make_pair(1, 0LL));
    for(int t = 0; t <= mxp; ++t) {
        memset(dp, 0x3f, sizeof(ll) * (n + 10));
        bs.reset();
        int sz = upd[t].size();
        for(int i = 0; i < sz; ++i) {
            up(dp[upd[t][i].first], upd[t][i].second);
            bs[upd[t][i].first] = true;
        }
        upd[t].clear();
        for(int i = bs._Find_first(); i != 100020; i = bs._Find_next(i)) {
            while(e[cur[i]].p < t && cur[i])
                cur[i] = nxt[cur[i]];
            for(int j = cur[i]; j ; j = nxt[j]) {
                upd[e[j].q].push_back(make_pair(e[j].to, g(e[j].p-t) + dp[i]));
                if(e[j].to == n) up(ans, g(e[j].p-t) + dp[i] + e[j].q);
            }
        }
    }
    write(ans);
    putchar('\n');

    return 0;
}

评测结果