提交记录 9811


用户 题目 状态 得分 用时 内存 语言 代码长度
Taduro noi19a. 【NOI2019】回家路线 Accepted 100 402.141 ms 354728 KB C++ 953 B
提交时间 评测时间
2019-07-16 17:06:28 2020-08-01 01:53:24
#include<cstdio>
#include<cstring>
#include<iostream>
#define ui unsigned int
const ui inf=2100000000;
using namespace std;
struct node{
	int next,to,p,q;
}w[200001];
ui f[1005][100001],A,B,C,ans;
int n,m,t,cnt,head[100001];
inline int calc(int x){return A*x*x+B*x+C;}
inline void add(int x,int y,int p,int q){
	w[++cnt].next=head[x];
	w[cnt].to=y; head[x]=cnt;
	w[cnt].p=p; w[cnt].q=q;
}
int main(){
	int x,y,p,q;
	scanf("%d%d%u%u%u",&n,&m,&A,&B,&C);
	for (int i=1; i<=m; i++){
		scanf("%d%d%d%d",&x,&y,&p,&q);
		add(x,y,p,q); t=max(t,q);
	}
	for(int i=0 ;i<=t; i++)
		for(int j=0; j<=n; j++)
			f[i][j]=inf;
	f[0][1]=0;
	for(int i=0; i<=t; i++)
		for(int j=1; j<=n; j++){
			if(f[i][j]==f[0][0]) continue;
			for (int k=head[j]; k; k=w[k].next){
				if (w[k].p<i) continue;
				f[w[k].q][w[k].to]=min(f[w[k].q][w[k].to],f[i][j]+calc(w[k].p-i));
			}
		}
	ans=f[0][0];
	for(int i=0; i<=t; i++) ans=min(ans,f[i][n]+i);
	printf("%u\n",ans);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1246.22 us2 MB + 228 KBAcceptedScore: 5

Testcase #2238.22 us2 MB + 52 KBAcceptedScore: 5

Testcase #3399.85 us4 MB + 148 KBAcceptedScore: 5

Testcase #4410.56 us4 MB + 204 KBAcceptedScore: 5

Testcase #52.794 ms10 MB + 408 KBAcceptedScore: 5

Testcase #62.819 ms10 MB + 412 KBAcceptedScore: 5

Testcase #72.895 ms10 MB + 400 KBAcceptedScore: 5

Testcase #82.859 ms10 MB + 308 KBAcceptedScore: 5

Testcase #92.795 ms10 MB + 356 KBAcceptedScore: 5

Testcase #102.732 ms10 MB + 340 KBAcceptedScore: 5

Testcase #112.845 ms10 MB + 432 KBAcceptedScore: 5

Testcase #123.416 ms10 MB + 460 KBAcceptedScore: 5

Testcase #132.94 ms10 MB + 360 KBAcceptedScore: 5

Testcase #143.316 ms10 MB + 360 KBAcceptedScore: 5

Testcase #15296.373 ms346 MB + 424 KBAcceptedScore: 5

Testcase #16266.468 ms346 MB + 424 KBAcceptedScore: 5

Testcase #17211.736 ms345 MB + 668 KBAcceptedScore: 5

Testcase #18121.791 ms346 MB + 424 KBAcceptedScore: 5

Testcase #19402.141 ms346 MB + 424 KBAcceptedScore: 5

Testcase #20135.381 ms346 MB + 424 KBAcceptedScore: 5


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