提交记录 9867


用户 题目 状态 得分 用时 内存 语言 代码长度
zengminghao noi19a. 【NOI2019】回家路线 Accepted 100 121.537 ms 394972 KB C++ 744 B
提交时间 评测时间
2019-07-18 15:33:00 2020-08-01 01:57:26
#include <bits/stdc++.h>
using namespace std;
int n, m, A, B, C, F[1003], f[100003][1003];
struct road {
	int x, y, p, q;
	bool operator < (const road &o) const {return p < o.p;}
} s[200003];
int main() {
	scanf("%d %d %d %d %d", &n, &m, &A, &B, &C);
	for (int i = 1; i <= m; i++)
		scanf("%d %d %d %d", &s[i].x, &s[i].y, &s[i].p, &s[i].q);
	for (int i = 0; i <= 1000; i++)
		F[i] = C + i * (B + i * A);
	sort(s + 1, s + m + 1);
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (register int i = 1; i <= m; i++)
		for (register int j = 0; j <= s[i].p; j++)
			f[s[i].y][s[i].q] = min(f[s[i].y][s[i].q], f[s[i].x][j] + F[s[i].p - j]);
	int ans = 2E9;
	for (int i = 0; i <= 1000; i++) ans = min(ans, f[n][i] + i);
	printf("%d\n", ans);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #132.073 ms382 MB + 684 KBAcceptedScore: 5

Testcase #232.075 ms382 MB + 684 KBAcceptedScore: 5

Testcase #332.066 ms382 MB + 684 KBAcceptedScore: 5

Testcase #432.077 ms382 MB + 684 KBAcceptedScore: 5

Testcase #533.681 ms382 MB + 744 KBAcceptedScore: 5

Testcase #633.725 ms382 MB + 744 KBAcceptedScore: 5

Testcase #733.687 ms382 MB + 744 KBAcceptedScore: 5

Testcase #833.686 ms382 MB + 744 KBAcceptedScore: 5

Testcase #933.655 ms382 MB + 744 KBAcceptedScore: 5

Testcase #1033.702 ms382 MB + 744 KBAcceptedScore: 5

Testcase #1133.719 ms382 MB + 744 KBAcceptedScore: 5

Testcase #1233.747 ms382 MB + 744 KBAcceptedScore: 5

Testcase #1333.708 ms382 MB + 744 KBAcceptedScore: 5

Testcase #1433.708 ms382 MB + 744 KBAcceptedScore: 5

Testcase #15119.003 ms385 MB + 732 KBAcceptedScore: 5

Testcase #16120.176 ms385 MB + 732 KBAcceptedScore: 5

Testcase #17120.975 ms385 MB + 732 KBAcceptedScore: 5

Testcase #18119.891 ms385 MB + 732 KBAcceptedScore: 5

Testcase #19119.123 ms385 MB + 732 KBAcceptedScore: 5

Testcase #20121.537 ms385 MB + 732 KBAcceptedScore: 5


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