代码

#include<bits/stdc++.h>

#define LL long long
#define RG register

using namespace std;
template<class T> inline void read(T &x) {
	x = 0; RG char c = getchar(); bool f = 0;
	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
	x = f ? -x : x;
	return ;
}
template<class T> inline void write(T x) {
	if (!x) {putchar(48);return ;}
	if (x < 0) x = -x, putchar('-');
	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 1e5 + 10;
const LL inf = 1e16;
struct node {
	int t, pos;
	LL val;
	bool operator < (const node &z) const {
		return t > z.t;
	}
};

const int __ = 5e6 + 10;
struct Heap {
	node h[__]; int siz;
	bool empty() { return !siz; }
	node top() { return h[1]; }
	void pop() { std::pop_heap(h + 1, h + siz + 1); --siz; }
	void push(node x) { h[++siz] = x; std::push_heap(h + 1, h + siz + 1); } 
} q;
int n, m, cur[N];
LL A, B, C;
struct Pair {
	int to, p, q;
	bool operator < (const Pair &z) const {
		return p < z.p;
	}
};
vector<Pair> e[N];
map<int, LL> f[N];
void solve() {
	f[1][0] = 0;
	q.push((node) {0, 1, 0});
	LL ans = inf;
	while (!q.empty()) {
		int u = q.top().pos, t = q.top().t; LL val = q.top().val; q.pop();
		if (val != f[u][t]) continue;
		if (u == n) ans = min(ans, val + t);
		while (cur[u] < e[u].size() && e[u][cur[u]].p < t) cur[u]++;
		for (int i = cur[u]; i < e[u].size(); i++) {
			int v = e[u][i].to, T = e[u][i].q;
			LL V = val + A * (e[u][i].p - t) * (e[u][i].p - t) + B * (e[u][i].p - t) + C;
			//printf("%d %d %d %d\n", v, T, V, f[v][T]);
			if (f[v][T] > V) {
				f[v][T] = V;
				q.push((node) {T, v, V});
			}
		}
	}
	printf("%lld\n", ans);
}
int main() {
	read(n), read(m), read(A), read(B), read(C);
	for (int i = 1, x, y, p, q; i <= m; i++) {
		read(x), read(y), read(p), read(q);
		f[y][q] = inf;
		e[x].push_back((Pair) {y, p, q});
	}
	for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());
	solve();
	return 0;
}

评测结果