代码

#include <bits/stdc++.h>
using namespace std;

// please, do not use C++11 features!

typedef long long ll;

const ll INF = 4e18;

const int MAXN = 1.1e5;
const int MAXM = 2.1e5;
int N, M;
ll A, B, C;
int X[MAXM], Y[MAXM];
ll P[MAXM], Q[MAXM];
int ord[MAXM];

bool cmp(int a, int b) {
	return Q[a] < Q[b];
}

struct line {
	ll m, b;
	line() { }
	line(ll _m, ll _b) : m(_m), b(_b) { }
	ll eval(ll x) const { return m * x + b; }

	bool operator < (const line& r) const {
		return b == r.b ? m < r.m : b < r.b;
	}
};

typedef long double ld;

// m increasing
bool bad(const line& a, const line& b, const line& c) {
	return (b.b - a.b) * (b.m - c.m) <= (c.b - b.b) * (a.m - b.m);
}

struct seg {
	seg* ch[2];
	vector<line> hull;

	seg() {
		ch[0] = ch[1] = NULL;
	}

	void insert(const line& l) {
		while (hull.size() >= 2 && bad(hull.end()[-2], hull.end()[-1], l)) {
			hull.pop_back();
		}
		hull.push_back(l);
	}

	ll slow_query(ll x) {
		ll res = hull[0].eval(x);
		for (size_t i = 1; i < hull.size(); i++) {
			res = min(res, hull[i].eval(x));
		}
		return res;
	}

	ll query(ll x) {
		if (hull.size() == 1) {
			return hull[0].eval(x);
		}
		int mi = 0, ma = hull.size()-1;
		while (ma - mi > 1) {
			int md = (mi + ma) / 2;
			if (hull[md].eval(x) >= hull[md-1].eval(x)) {
				ma = md;
			} else {
				mi = md;
			}
		}
		ll res = hull[ma].eval(x);
		if (ma >= 1) {
			res = min(res, hull[ma-1].eval(x));
		}
		return res;
	}
};

seg* roots[MAXN];

int V;
vector<int> vals;
int get(int x) {
	return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}

void insert(int p, const line& l, seg* &r, int x = 0, int y = V) {
	if (!r) {
		r = new seg;
	}
	r->insert(l);

	if (y - x > 1) {
		int z = (x + y) / 2;
		if (p < z) {
			insert(p, l, r->ch[0], x, z);
		} else {
			insert(p, l, r->ch[1], z, y);
		}
	}
}

void query(int l, int r, ll v, seg* n, ll& res, int x = 0, int y = V) {
	if (!n) return;
	if (l <= x && y <= r) {
		res = min(res, n->query(v));
	} else {
		int z = (x + y) / 2;
		if (l < z) {
			query(l, r, v, n->ch[0], res, x, z);
		}
		if (z < r) {
			query(l, r, v, n->ch[1], res, z, y);
		}
	}
}

vector<line> buf[MAXN];

int main() {
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);

	scanf("%d %d %lld %lld %lld", &N, &M, &A, &B, &C);
	X[0] = Y[0] = 1;
	P[0] = Q[0] = 0;
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %lld %lld", &X[i], &Y[i], &P[i], &Q[i]);
		ord[i] = i;
	}

	for (int i = 0; i <= M; i++) {
		vals.push_back(P[i]);
		vals.push_back(Q[i]);
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	V = vals.size();

	sort(ord + 1, ord + M + 1, cmp);
	insert(get(0), line(0, 0), roots[1]);

	ll ans = INF;
	for (int st = 1; st <= M; ) {
		int ed = st;
		for (; ed <= M && Q[ord[st]] == Q[ord[ed]]; ed++);

		set<int> inds;
		for (int i1 = st; i1 < ed; i1++) {
			int i = ord[i1];
			ll best = INF;
			query(0, get(P[i]) + 1, -2 * A * P[i], roots[X[i]], best); // something
			best += (A * P[i] + B) * P[i] + C;
			best = min(best, INF);

			if (best == INF) continue;

			if (Y[i] == N) {
				ans = min(ans, best + Q[i]);
			}

			line l(Q[i], best + (A * Q[i] - B) * Q[i]);
			inds.insert(Y[i]);
			buf[Y[i]].push_back(l);
		}

		for (set<int>::iterator it = inds.begin(); it != inds.end(); ++it) {
			int y = *it;
			sort(buf[y].begin(), buf[y].end());
			for (size_t i = 0; i < buf[y].size(); i++) {
				if (i == 0 || buf[y][i-1].m != buf[y][i].m) {
					insert(get(buf[y][i].m), buf[y][i], roots[y]);
				}
			}
			buf[y].clear();
		}

		st = ed;
	}
	printf("%lld\n", ans);

	return 0;
}

评测结果