代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back

int n,m,A,B,C,ans=2e9;
int p[200010],q[200010],X[200010],Y[200010];
vector<int> c1[1010],c2[1010];
int f[200010],g[200010];
struct Queue{
	vector<int> s;
	int st,ed;
	Queue():st(0),ed(-1){}
	bool empty(){return st>ed;}
	int front(){return s[st];}
	void add(int x){
		while(st<ed&& 1ll*(g[s[ed]]-g[s[ed-1]])*(q[x]-q[s[ed]]) >= 1ll*(g[x]-g[s[ed]])*(q[s[ed]]-q[s[ed-1]]))ed--;
		if(s.size()-1==ed)s.pb(0);
		s[++ed]=x;
	}
	void del(int x){
		while(st<ed&& (g[s[st+1]]-g[s[st]]) < 1ll*x*(q[s[st+1]]-q[s[st]]) )st++;
	}
}Q[100010];

int main()
{
	scanf("%d %d %d %d %d",&n,&m,&A,&B,&C);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d %d",&X[i],&Y[i],&p[i],&q[i]);
		c1[p[i]].pb(i);
		c2[q[i]].pb(i);
	}
	memset(f,63,sizeof(f));
	memset(g,63,sizeof(g));//g也要初始化，别忘了
	f[0]=0;g[0]=0;Q[1].add(0);
	for(int Ti=0;Ti<=1000;Ti++){
		for(int i:c2[Ti]){//注意要先处理c2，即先将点加入队列，下面的c1可能用到
			if(Y[i]==n)ans=min(ans,f[i]+q[i]);
			else Q[Y[i]].add(i);
		}
		for(int i:c1[Ti]){
			if(!Q[X[i]].empty()){
				Q[X[i]].del(2*A*p[i]);
				int j=Q[X[i]].front();
				f[i]=f[j]+A*(p[i]-q[j])*(p[i]-q[j])+B*(p[i]-q[j])+C;
				g[i]=f[i]+A*q[i]*q[i]-B*q[i];
			}
		}
	}
	printf("%d",ans);
}

评测结果