提交记录 9810


用户 题目 状态 得分 用时 内存 语言 代码长度
xgcxgc noi19a. 【NOI2019】回家路线 Accepted 100 696.437 ms 200716 KB C++ 1.71 KB
提交时间 评测时间
2019-07-16 17:05:22 2020-08-01 01:53:20
#include <bits/stdc++.h>

#define LL long long
#define pa pair<int,int>
using namespace std;
const int inf = 2147483647;
const int N = 100001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct node {int x, y, st, ed;} a[N * 2];
struct edge {
	int y, t1, t2;
}; vector<edge> q[N];
int f[N][1001];
int s[1001];

bool cmp(node a, node b) {return a.st > b.st;}

int main() {
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	int n = read(), m = read(), A = read(), B = read(), C = read();
	int maxx = 0;
	for(int i = 1; i <= m; i++) a[i].x = read(), a[i].y = read(), a[i].st = read(), a[i].ed = read();
	sort(a + 1, a + m + 1, cmp);
	for(int i = 1; i <= m; i++) {
		q[a[i].x].push_back(edge{a[i].y, a[i].st, a[i].ed});
		maxx = _max(maxx, a[i].ed);
	} for(int i = 0; i <= maxx; i++) s[i] = A * i * i + B * i + C;
	f[1][0] = 1;
	for(int i = 0; i <= maxx; i++) {
		for(int x = 1; x <= n; x++) if(f[x][i] != 0){
			for(int k = 0; k < q[x].size(); k++) {
				int t1 = q[x][k].t1, t2 = q[x][k].t2;
				if(t1 < i) break;
				int y = q[x][k].y;
				if(f[y][t2] == 0) f[y][t2] = f[x][i] + s[t1 - i];
				else f[y][t2] = _min(f[y][t2], f[x][i] + s[t1 - i]);
			}
		}
	} int ans = 0;
	for(int i = 0; i <= maxx; i++) if(f[n][i] != 0){
		if(ans == 0) ans = f[n][i] + i;
		else ans = _min(ans, f[n][i] + i);
	}
	put(ans - 1), puts("");
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1512.85 us2 MB + 736 KBAcceptedScore: 5

Testcase #2506.79 us2 MB + 736 KBAcceptedScore: 5

Testcase #3464.81 us2 MB + 604 KBAcceptedScore: 5

Testcase #4455.27 us2 MB + 596 KBAcceptedScore: 5

Testcase #58.796 ms3 MB + 732 KBAcceptedScore: 5

Testcase #68.955 ms6 MB + 364 KBAcceptedScore: 5

Testcase #78.884 ms5 MB + 564 KBAcceptedScore: 5

Testcase #88.917 ms7 MB + 4 KBAcceptedScore: 5

Testcase #98.865 ms5 MB + 864 KBAcceptedScore: 5

Testcase #108.626 ms2 MB + 604 KBAcceptedScore: 5

Testcase #118.826 ms3 MB + 892 KBAcceptedScore: 5

Testcase #128.934 ms5 MB + 60 KBAcceptedScore: 5

Testcase #138.815 ms4 MB + 280 KBAcceptedScore: 5

Testcase #148.873 ms5 MB + 360 KBAcceptedScore: 5

Testcase #15615.662 ms144 MB + 592 KBAcceptedScore: 5

Testcase #16608.548 ms130 MB + 504 KBAcceptedScore: 5

Testcase #17577.877 ms86 MB + 224 KBAcceptedScore: 5

Testcase #18569.701 ms20 MB + 564 KBAcceptedScore: 5

Testcase #19696.437 ms196 MB + 12 KBAcceptedScore: 5

Testcase #20571.95 ms43 MB + 536 KBAcceptedScore: 5


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