代码

#include<bits/stdc++.h>
using namespace std;
int n,m,A,B,C,dp[222222],head[111111],tail[111111],k[222222],b[222222],nxt[222222],pre[222222],pos,cnt,xx,yy,ans;
bool cant[222222];
struct edge
{
	int x,y,p,q,id;
}ed[222222],ed2[222222];
bool cmp1(edge a,edge b)
{
	return (a.q>b.q);
}
bool cmp2(edge a,edge b)
{
	return (a.p>b.p);
}
void add(int p)
{
	edge u=ed2[p];
	++cnt;k[cnt]=2*A*u.p;b[cnt]=A*u.p*u.p+B*u.p+dp[u.id];
	while(head[u.x] && head[u.x]!=tail[u.x])
	{
		xx=tail[u.x];yy=pre[xx];
		if (1ll*(k[xx]-k[cnt])*(b[yy]-b[xx])<=1ll*(b[xx]-b[cnt])*(k[yy]-k[xx])) 
		{
			tail[u.x]=yy;
		}
		else break;
	}
	if (tail[u.x]) nxt[tail[u.x]]=cnt;
	pre[cnt]=tail[u.x];
	tail[u.x]=cnt;
	if (!head[u.x]) head[u.x]=cnt;
}
int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&ed[i].x,&ed[i].y,&ed[i].p,&ed[i].q);
		ed[i].id=i;ed2[i]=ed[i];
	}
	sort(ed+1,ed+m+1,cmp1);pos=1;sort(ed2+1,ed2+m+1,cmp2);
	for (int i=1;i<=m;i++)
	{
		int id=ed[i].id;
		if (ed[i].y==n) dp[id]=ed[i].q;
		else
		{
			while(pos<=m && ed2[pos].p>=ed[i].q) 
			{
				if (!cant[ed2[pos].id]) add(pos);
				pos++;
			}
			if (!head[ed[i].y])
			{
				cant[id]=1;
				continue;
			}
			while(head[ed[i].y]!=tail[ed[i].y])
			{
				xx=head[ed[i].y];yy=nxt[xx];
				if (-k[xx]*ed[i].q+b[xx]>=k[yy]*ed[i].q+b[yy]) 
				{
					head[ed[i].y]=yy;
				}
				else break;
			}
			xx=head[ed[i].y];
			dp[id]=-k[xx]*ed[i].q+b[xx]+A*ed[i].q*ed[i].q-B*ed[i].q+C;
		}
	}
	ans=2147483647;
	for (int i=1;i<=m;i++)
	{
		int id=ed[i].id;
		if (ed[i].x==1 && !cant[id]) ans=min(ans,dp[id]+A*ed[i].p*ed[i].p+B*ed[i].p+C);
	}
	printf("%d\n",ans);
	return 0;
}

评测结果