提交记录 9797


用户 题目 状态 得分 用时 内存 语言 代码长度
skylee noi19a. 【NOI2019】回家路线 Accepted 100 150.939 ms 394152 KB C++ 1.10 KB
提交时间 评测时间
2019-07-16 14:13:28 2020-08-01 01:51:53
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=1e5+1,M=2e5+1,T=1e3+1;
int n,m,A,B,C,f[N][T];
struct Edge {
	int u,v,p,q;
	bool operator < (const Edge &rhs) const {
		return p<rhs.p;
	}
};
Edge e[M];
inline int calc(const int &x) {
	return A*x*x+B*x+C;
}
inline void upd(int &a,const int &b) {
	a=std::min(a,b);
}
int main() {
	n=getint(),m=getint();
	A=getint(),B=getint(),C=getint();
	for(register int i=1;i<=m;i++) {
		const int u=getint(),v=getint(),p=getint(),q=getint();
		e[i]=(Edge){u,v,p,q};
	}
	for(register int i=1;i<=n;i++) {
		std::fill(&f[i][0],&f[i][T],INT_MAX);
	}
	f[1][0]=0;
	std::sort(&e[1],&e[m]+1);
	for(register int i=1;i<=m;i++) {
		for(register int j=0;j<=e[i].p;j++) {
			if(f[e[i].u][j]==INT_MAX) continue;
			upd(f[e[i].v][e[i].q],f[e[i].u][j]+calc(e[i].p-j));
		}
	}
	int ans=INT_MAX;
	for(register int i=0;i<T;i++) {
		if(f[n][i]!=INT_MAX) upd(ans,f[n][i]+i);
	}
	printf("%d\n",ans);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #190.7 us412 KBAcceptedScore: 5

Testcase #289.75 us412 KBAcceptedScore: 5

Testcase #365.74 us272 KBAcceptedScore: 5

Testcase #463.37 us264 KBAcceptedScore: 5

Testcase #52.504 ms7 MB + 720 KBAcceptedScore: 5

Testcase #62.539 ms7 MB + 712 KBAcceptedScore: 5

Testcase #72.527 ms7 MB + 712 KBAcceptedScore: 5

Testcase #82.538 ms7 MB + 732 KBAcceptedScore: 5

Testcase #92.52 ms7 MB + 704 KBAcceptedScore: 5

Testcase #102.468 ms7 MB + 700 KBAcceptedScore: 5

Testcase #112.503 ms7 MB + 724 KBAcceptedScore: 5

Testcase #122.553 ms7 MB + 728 KBAcceptedScore: 5

Testcase #132.529 ms7 MB + 724 KBAcceptedScore: 5

Testcase #142.546 ms7 MB + 724 KBAcceptedScore: 5

Testcase #15143.7 ms384 MB + 908 KBAcceptedScore: 5

Testcase #16144.651 ms384 MB + 936 KBAcceptedScore: 5

Testcase #17140.496 ms384 MB + 928 KBAcceptedScore: 5

Testcase #18139.097 ms384 MB + 920 KBAcceptedScore: 5

Testcase #19150.939 ms384 MB + 920 KBAcceptedScore: 5

Testcase #20140.833 ms384 MB + 928 KBAcceptedScore: 5


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