代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,A,B,C,cnt=0;
struct Thing{
	int x,y,p,q;
	bool operator <(const Thing yy) const {
		return p<yy.p;
	}
}a[200005];
vector<int> rl[200005],id[200005];
long long f[200005],ans=0x3f3f3f3f3f3f3f3fll;
int F(int x){
	return A*x*x+B*x+C;
}
int main() {
	cin>>n>>m>>A>>B>>C;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].p,&a[i].q);
		rl[a[i].y].push_back(a[i].q);
	}
	rl[1].push_back(0);
	for(int i=1;i<=n;i++){
		sort(rl[i].begin(),rl[i].end());
		int tmp=unique(rl[i].begin(),rl[i].end())-rl[i].begin();
		rl[i].resize(tmp);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<rl[i].size();j++){
			id[i].push_back(++cnt);
		}
	}
	memset(f,0x3f,sizeof(f));
	f[1]=0;
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++){
		int fr=a[i].x,to=a[i].y,now;
		for(int j=0;j<rl[to].size();j++)if(rl[to][j]==a[i].q)now=id[to][j];
		for(int j=0;j<rl[fr].size();j++){
			if(rl[fr][j]>a[i].p)break;
			int ps=id[fr][j];
			f[now]=min(f[now],f[ps]+F(a[i].p-rl[fr][j]));
		}
	}
	for(int i=0;i<rl[n].size();i++){
		ans=min(ans,f[id[n][i]]+rl[n][i]);
	}
	printf("%lld\n",ans);
	return 0;
}

评测结果