提交记录 12856


用户 题目 状态 得分 用时 内存 语言 代码长度
luosiyuan noi19a. 【NOI2019】回家路线 Accepted 100 166.396 ms 18 MB + 768 KB C++11 1.16 KB
提交时间 评测时间
2020-06-13 19:43:05 2020-08-01 03:00:18
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,A,B,C,cnt=0;
struct Thing{
	int x,y,p,q;
	bool operator <(const Thing yy) const {
		return p<yy.p;
	}
}a[200005];
vector<int> rl[200005],id[200005];
long long f[200005],ans=0x3f3f3f3f3f3f3f3fll;
int F(int x){
	return A*x*x+B*x+C;
}
int main() {
	cin>>n>>m>>A>>B>>C;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].p,&a[i].q);
		rl[a[i].y].push_back(a[i].q);
	}
	rl[1].push_back(0);
	for(int i=1;i<=n;i++){
		sort(rl[i].begin(),rl[i].end());
		int tmp=unique(rl[i].begin(),rl[i].end())-rl[i].begin();
		rl[i].resize(tmp);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<rl[i].size();j++){
			id[i].push_back(++cnt);
		}
	}
	memset(f,0x3f,sizeof(f));
	f[1]=0;
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++){
		int fr=a[i].x,to=a[i].y,now;
		for(int j=0;j<rl[to].size();j++)if(rl[to][j]==a[i].q)now=id[to][j];
		for(int j=0;j<rl[fr].size();j++){
			if(rl[fr][j]>a[i].p)break;
			int ps=id[fr][j];
			f[now]=min(f[now],f[ps]+F(a[i].p-rl[fr][j]));
		}
	}
	for(int i=0;i<rl[n].size();i++){
		ans=min(ans,f[id[n][i]]+rl[n][i]);
	}
	printf("%lld\n",ans);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.787 ms10 MB + 748 KBAcceptedScore: 5

Testcase #21.782 ms10 MB + 748 KBAcceptedScore: 5

Testcase #31.776 ms10 MB + 744 KBAcceptedScore: 5

Testcase #41.787 ms10 MB + 744 KBAcceptedScore: 5

Testcase #53.755 ms10 MB + 892 KBAcceptedScore: 5

Testcase #63.05 ms10 MB + 904 KBAcceptedScore: 5

Testcase #73.828 ms10 MB + 896 KBAcceptedScore: 5

Testcase #83.247 ms10 MB + 904 KBAcceptedScore: 5

Testcase #93.837 ms10 MB + 896 KBAcceptedScore: 5

Testcase #103.017 ms10 MB + 908 KBAcceptedScore: 5

Testcase #114.264 ms10 MB + 900 KBAcceptedScore: 5

Testcase #123.737 ms10 MB + 912 KBAcceptedScore: 5

Testcase #133.948 ms10 MB + 908 KBAcceptedScore: 5

Testcase #144.119 ms10 MB + 904 KBAcceptedScore: 5

Testcase #15166.396 ms18 MB + 548 KBAcceptedScore: 5

Testcase #16144.104 ms18 MB + 752 KBAcceptedScore: 5

Testcase #17166.231 ms18 MB + 548 KBAcceptedScore: 5

Testcase #18142.642 ms18 MB + 764 KBAcceptedScore: 5

Testcase #19162.625 ms18 MB + 576 KBAcceptedScore: 5

Testcase #20142.898 ms18 MB + 768 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2020-08-14 13:44:26 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用