提交记录 12971


用户 题目 状态 得分 用时 内存 语言 代码长度
lqs2015 noi19a. 【NOI2019】回家路线 Accepted 100 55.396 ms 10344 KB C++ 1.67 KB
提交时间 评测时间
2020-07-11 10:49:32 2020-08-01 03:02:27
#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;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #160.1 us68 KBAcceptedScore: 5

Testcase #265.76 us68 KBAcceptedScore: 5

Testcase #358.71 us76 KBAcceptedScore: 5

Testcase #456.97 us76 KBAcceptedScore: 5

Testcase #51.052 ms280 KBAcceptedScore: 5

Testcase #61.033 ms264 KBAcceptedScore: 5

Testcase #71.036 ms276 KBAcceptedScore: 5

Testcase #81.048 ms268 KBAcceptedScore: 5

Testcase #91.038 ms276 KBAcceptedScore: 5

Testcase #101.037 ms264 KBAcceptedScore: 5

Testcase #111.064 ms280 KBAcceptedScore: 5

Testcase #121.052 ms264 KBAcceptedScore: 5

Testcase #131.067 ms280 KBAcceptedScore: 5

Testcase #141.076 ms280 KBAcceptedScore: 5

Testcase #1554.516 ms10 MB + 24 KBAcceptedScore: 5

Testcase #1654.907 ms10 MB + 104 KBAcceptedScore: 5

Testcase #1754.398 ms8 MB + 104 KBAcceptedScore: 5

Testcase #1853.247 ms9 MB + 652 KBAcceptedScore: 5

Testcase #1953.321 ms9 MB + 572 KBAcceptedScore: 5

Testcase #2055.396 ms9 MB + 892 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 11:01:50 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用