代码

#include <bits/stdc++.h>

#define LL long long
#define pa pair<int,int>
using namespace std;
const int inf = 2147483647;
const int N = 100001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct node {int x, y, st, ed;} a[N * 2];
struct edge {
	int y, t1, t2;
}; vector<edge> q[N];
int f[N][1001];
int s[1001];

bool cmp(node a, node b) {return a.st > b.st;}

int main() {
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	int n = read(), m = read(), A = read(), B = read(), C = read();
	int maxx = 0;
	for(int i = 1; i <= m; i++) a[i].x = read(), a[i].y = read(), a[i].st = read(), a[i].ed = read();
	sort(a + 1, a + m + 1, cmp);
	for(int i = 1; i <= m; i++) {
		q[a[i].x].push_back(edge{a[i].y, a[i].st, a[i].ed});
		maxx = _max(maxx, a[i].ed);
	} for(int i = 0; i <= maxx; i++) s[i] = A * i * i + B * i + C;
	f[1][0] = 1;
	for(int i = 0; i <= maxx; i++) {
		for(int x = 1; x <= n; x++) if(f[x][i] != 0){
			for(int k = 0; k < q[x].size(); k++) {
				int t1 = q[x][k].t1, t2 = q[x][k].t2;
				if(t1 < i) break;
				int y = q[x][k].y;
				if(f[y][t2] == 0) f[y][t2] = f[x][i] + s[t1 - i];
				else f[y][t2] = _min(f[y][t2], f[x][i] + s[t1 - i]);
			}
		}
	} int ans = 0;
	for(int i = 0; i <= maxx; i++) if(f[n][i] != 0){
		if(ans == 0) ans = f[n][i] + i;
		else ans = _min(ans, f[n][i] + i);
	}
	put(ans - 1), puts("");
	return 0;
}

评测结果