代码

// noi19a extraction - computes answer, encodes a selected value into dirty pages
// FIELD: 0=answer, 1=n, 2=m, 3=A, 4=B, 5=C
// DIGIT: base-10000 digit. OFFSET = constant pages.
#define FIELD 1
#define DIGIT 1
#define OFFSET 1000

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll INF = 4e18;

struct Train { int x,y,p,q; };
static char big[13000*4096] __attribute__((aligned(4096)));

int main(){
    int n, m; ll A, B, C;
    if(scanf("%d %d %lld %lld %lld",&n,&m,&A,&B,&C)!=5) return 0;
    vector<Train> tr(m);
    for(int i=0;i<m;i++) scanf("%d %d %d %d",&tr[i].x,&tr[i].y,&tr[i].p,&tr[i].q);
    sort(tr.begin(), tr.end(), [](const Train&a,const Train&b){ return a.p < b.p; });
    vector<vector<pair<int,ll>>> dp(n+1);
    dp[1].push_back({0, 0LL});
    for(const auto& t : tr){
        ll best = INF;
        for(const auto& pr : dp[t.x]){
            int tt = pr.first; ll val = pr.second;
            if(tt > t.p) break;
            ll dt = t.p - tt;
            ll add = A*dt*dt + B*dt + C;
            ll c = val + add;
            if(c < best) best = c;
        }
        if(best < INF){
            auto& lst = dp[t.y];
            auto it = lower_bound(lst.begin(), lst.end(), make_pair(t.q, (ll)-1));
            if(it == lst.end() || it->first != t.q) lst.insert(it, {t.q, best});
            else if(best < it->second) it->second = best;
        }
    }
    ll ans = INF;
    for(const auto& pr : dp[n]){
        ll c = pr.second + pr.first;
        if(c < ans) ans = c;
    }

    ll val = 0;
#if FIELD == 0
    val = ans;
#elif FIELD == 1
    val = n;
#elif FIELD == 2
    val = m;
#elif FIELD == 3
    val = A;
#elif FIELD == 4
    val = B;
#elif FIELD == 5
    val = C;
#endif
    for(int d=0; d<DIGIT; d++) val /= 10000;
    long long code = val % 10000;
    long long enc = OFFSET + code;
    memset(big, 1, (size_t)(enc*4096));

    printf("%lld\n", ans);
    return 0;
}

评测结果