提交记录 9799


用户 题目 状态 得分 用时 内存 语言 代码长度
xuanyiming noi19a. 【NOI2019】回家路线 Accepted 100 236.074 ms 395740 KB C++ 873 B
提交时间 评测时间
2019-07-16 14:14:01 2020-08-01 01:52:23
#include<bits/stdc++.h>
using namespace std;
const int N=100005,INF=1062000000;
struct Ask{
	int x,y,p,q;
}A[N*2];
int dp[N][1005],n,m,a,b,c;
inline int solve(int x){
	return a*x*x+b*x+c;
}
inline int cmp(Ask x,Ask y){
	return x.p<y.p;
}
inline int read(){
	int x=0;char c=0;
	for (;c<'0'||c>'9';c=getchar());
	for (;c>='0'&&c<='9';c=getchar())x=x*10+c-48;
	return x;
} 
int main(){
	n=read();m=read();a=read();b=read();c=read();
	for (int i=1;i<=m;i++)
		A[i].x=read(),A[i].y=read(),A[i].p=read(),A[i].q=read();
	sort(A+1,A+m+1,cmp);
	int T=1000;
	for (int i=1;i<=n;i++)
		for (int j=0;j<=T;j++)dp[i][j]=INF;
	for (int i=0;i<=T;i++)dp[1][i]=solve(i);
	for (int i=1;i<=m;i++)
		for (int j=A[i].q;j<=T;j++)
			dp[A[i].y][j]=min(dp[A[i].y][j],dp[A[i].x][A[i].p]+
			solve(j-A[i].q));
	int Ans=INF+T;
	for (int i=0;i<=T;i++)Ans=min(Ans,dp[n][i]+i);
	printf("%d\n",Ans-c);		
} 

CompilationN/AN/ACompile OKScore: N/A

Testcase #1193.34 us444 KBAcceptedScore: 5

Testcase #2201.83 us444 KBAcceptedScore: 5

Testcase #3164.9 us308 KBAcceptedScore: 5

Testcase #4157.42 us300 KBAcceptedScore: 5

Testcase #54.304 ms7 MB + 784 KBAcceptedScore: 5

Testcase #64.294 ms7 MB + 776 KBAcceptedScore: 5

Testcase #74.247 ms7 MB + 776 KBAcceptedScore: 5

Testcase #84.31 ms7 MB + 796 KBAcceptedScore: 5

Testcase #94.275 ms7 MB + 768 KBAcceptedScore: 5

Testcase #104.301 ms7 MB + 764 KBAcceptedScore: 5

Testcase #114.318 ms7 MB + 788 KBAcceptedScore: 5

Testcase #124.314 ms7 MB + 792 KBAcceptedScore: 5

Testcase #134.315 ms7 MB + 788 KBAcceptedScore: 5

Testcase #144.311 ms7 MB + 788 KBAcceptedScore: 5

Testcase #15233.634 ms386 MB + 452 KBAcceptedScore: 5

Testcase #16235.28 ms386 MB + 476 KBAcceptedScore: 5

Testcase #17234.53 ms386 MB + 468 KBAcceptedScore: 5

Testcase #18235.07 ms386 MB + 460 KBAcceptedScore: 5

Testcase #19233.813 ms386 MB + 460 KBAcceptedScore: 5

Testcase #20236.074 ms386 MB + 468 KBAcceptedScore: 5


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