代码

#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for(int i = (a), i##end = (b); i <= i##end; ++ i)
#define CLR(i, a) memset(i, a, sizeof(i))
#define REPD(i, a, b) for(int i = (a), i##end = (b); i >= i##end; -- i)
#define LOG(x) std::cerr << #x << ":" << x << '\n'
#define DBG(...) fprintf(stderr, __VA_ARGS__)
#define OK fprintf(stderr, "Passing %s in LINE [%d]\n", __FUNCTION__, __LINE__)
typedef double DB;
DB _BEGIN;
#define _TIME (int((clock() - _BEGIN) / (DB)CLOCKS_PER_SEC * 1000))
#define gc getchar
#define pc putchar
#define endl '\n'
typedef long long LL;
inline LL rd() {
	char ch = gc(); LL ret = 0, sgn = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') sgn = -1;
		ch = gc();
	}
	while(ch <= '9' && ch >= '0') 
		ret = ret * 10 + ch - '0', ch = gc();
	return ret * sgn;
}
inline void out(LL x) {
	static int buf[50], btp;
	if(x < 0) x = -x, pc('-');
	if(!x) pc('0');
	else {
		btp = 0;
		for(; x; x /= 10) buf[++ btp] = x % 10;
		while(btp) pc('0' + buf[btp --]);
	}
}
/**************************************************************/

const int N = 1e5 + 3, M = 2e5 + 3, V = 1e3 + 3;

struct Edge {
	int v; LL w;
	Edge() {}
	Edge(int _v, LL _w) : v(_v), w(_w) {}
} ;
vector<Edge> vec[M << 2];
int idcnt, id[N][V];
LL ds[M << 2];
const LL INF = 1e17;
int n, m, A, B, C;

struct Event {
	int x, y, p, q;
} prc[M];

inline LL F(LL g) {
	return A * g * g + B * g + C;
}
inline void add(int x, int y, LL c) {
	// DBG("%d %d: %lld\n", y, x, c);
	vec[x].push_back(Edge(y, c));
}


bool vis[M << 2];
LL Dfs(int x) {
	if(vis[x]) return ds[x];
	vis[x] = 1;
	ds[x] = INF;
	LL &ret = ds[x];
	REP(i, 0, vec[x].size() - 1) {
		LL w = vec[x][i].w, v = vec[x][i].v;
		ret = min(ret, w + Dfs(v));
	} 
	// LOG(ret), LOG(x);
	return ret;
}

vector<int> fk[N], idd[N];;
int main() {
#ifndef LOCAL
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
#endif
	int mx = 0;
	n = rd(), m = rd(), A = rd(), B = rd(), C = rd();
	REP(i, 1, m) {
		int x = rd(), y = rd(), p = rd(), q = rd();
		prc[i] = (Event) { x, y, p, q };
		if(!id[x][p]) id[x][p] = ++ idcnt, idd[x].push_back(p);
		if(!id[y][q]) id[y][q] = ++ idcnt, idd[y].push_back(q);
		if(!id[x][q]) id[x][q] = ++ idcnt, idd[x].push_back(q);
		if(!id[y][p]) id[y][p] = ++ idcnt, idd[y].push_back(p);
		mx = max(p, mx);
		mx = max(mx, q);
		fk[x].push_back(i);
	}
	REP(i, 1, n) sort(idd[i].begin(), idd[i].end());

	REP(i, 1, m) {
		int p = prc[i].p, q = prc[i].q;
		int x = prc[i].x, y = prc[i].y;
		if(x != 1) REP(lft, 0, idd[x].size() - 1) {
			int hh = idd[x][lft], hhh = q;
			if(hh > p) break;
			add(id[y][hhh], id[x][hh], F(p - hh));
		} else {
			add(id[y][q], id[x][p], F(p));
		}

	}
	REP(i, 0, mx) if(id[1][i]) {
		vis[id[1][i]] = 1, ds[id[1][i]] = 0;
	}

	LL ans = INF;
	REP(i, 0, mx) if(id[n][i]) {
		// LOG(i);
		if(!vis[id[n][i]]) Dfs(id[n][i]);
		if(ds[id[n][i]] < INF) {
			ans = min(ans, ds[id[n][i]] + i);
		}
	}

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

评测结果