代码

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<vector>
#include<deque>
#include<iostream>
#include<algorithm>

#define rg register
#define il inline
#define MX (200000 + 5)
#define db double
#define INF (1LL << 50)
#define ll long long

ll min(ll a ,ll b){return a < b ? a : b;}

int n ,m ,A ,B ,C;
il int read(){
	rg char k = getchar();
	int x = 0;
	while(k < '0' || k > '9')	k = getchar();
	while(k >= '0' && k <= '9'){
		x = x * 10 + k - '0';
		k = getchar();
	}
	return x;
}
struct edge{
	int x ,y ,p ,q;
	long long val;
}e[MX];
struct operation{
	int pos ,tim ,id ,belong;
	bool operator <(const operation &B)const{return tim == B.tim ? id > B.id : tim < B.tim;}
}op[MX * 2];

std::deque<int> que[MX >> 1];
ll dp[MX * 2];
db slope(int j1 ,int j2){
	if(op[j1].tim - op[j2].tim == 0)	return INF;
	return (dp[j1] - dp[j2] * 1.0) / (op[j1].tim - op[j2].tim);
}

void stop(){
	for(rg int i = 1 ; i <= 100 ;)
		++i;
}

int main(){
	//freopen("route7.in" ,"r" ,stdin);
	n = read(); m = read();
	A = read(); B = read(); C = read();
	for(rg int i = 1 ,x ,y ,p ,q ; i <= m ; ++i){
		x = read(); y = read();
		p = read(); q = read();
		e[i] = (edge){x ,y ,p ,q ,0};
		op[i * 2 - 1] = (operation){x ,p ,1 ,i};
		op[i * 2] = (operation){y ,q ,2 ,i};
	}
	ll ans = INF;
	std::sort(op + 1 ,op + 1 + m + m);
	e[0] = (edge){0 ,1 ,0 ,0};
	op[0] = (operation){1 ,0 ,2 ,0};
	que[1].push_back(0);
	for(int i = 1 ,now ,type ; i <= m * 2 ; ++i){
		now = op[i].pos ,type = op[i].id;
		if(now == 617) stop();
		if(type == 1){
			while(que[now].size() > 1){
				int j1 = que[now].front() ,j2 = que[now].at(1);
				ll t = 1LL * A * (2 * op[i].tim - op[j1].tim - op[j2].tim) + B;
				if(slope(j1 ,j2) <= t)	que[now].pop_front();
				else break;
			}
			
			if(!que[now].empty()){
				int j = que[now].front();
				e[op[i].belong].val = dp[j] + 
					1LL * A * (op[i].tim - op[j].tim) * (op[i].tim - op[j].tim) 
					+ 1LL * B * (op[i].tim - op[j].tim) + C;
			}
			else{e[op[i].belong].val = INF; continue;}
		}
		
		else{
			dp[i] = e[op[i].belong].val;
			while(que[now].size() > 1){
				int j1 = que[now].back() ,j2 = que[now].at(que[now].size() - 2);
				if(slope(j1 ,i) < slope(j2 ,j1))	que[now].pop_back();
				else break;
			}
			
			if(now == n){
			 	ans = min(ans ,dp[i] + op[i].tim);
				//std::cerr << "One reaches End. From " << e[op[i].belong].x << ". Answer is " << dp[i] + op[i].tim << " \n";
			 	continue;
			}
			 
			if(dp[i] < INF)	{
				//std::cerr << "Reached " << now << ". Answer is " << dp[i] << ". Time is " << op[i].tim << " \n";
				que[now].push_back(i);
			}
		}
		
	}
	printf("%lld\n" ,ans);
	return 0;
}

评测结果