蒟蒻75pts求助,为什么会wa啊()
查看原帖
蒟蒻75pts求助,为什么会wa啊()
747916
jingyu0929楼主2023/5/18 15:55

不是正解,但不知道dfs爆搜为什么不会TLE而是会wa。

#include<bits/stdc++.h>
using namespace std;
typedef long long lwl;

const int N = 1e5 + 5, inf = 0x3f3f3f3f;

struct node{
	int v,be,en;
};

int n,m,A,B,C;
vector<node> e[N];
int ans = 2e9;
int dfs[N];

lwl fr(){
	lwl x = 0, flag = 1;
	char t;
	t = getchar();
	while (t < 48 || t > 57){
		if (t == '-') flag = -1;
		t = getchar();
	}
	while (t >= 48 && t <= 57){
		x = x * 10 + t - 48;
		t = getchar();
	}
	return x*flag;
}

void fw(lwl x){
	if (x < 0) putchar('-'),x = -x;
	if (x > 9){
		fw(x / 10);
	}
	putchar(x % 10 + '0');
	return ;
}

int get(int q,int p) {
	return A * (p - q) * (p - q) + B * (p - q) + C;
}

void dfss(int u,int tim) {
	for (auto &it : e[u]) {
		int be = it.be,en = it.en,v = it.v;
		if (tim > be) continue;
		if (v != n) {
			dfs[v] = dfs[u] + get(tim,be);
			if (dfs[v] >= ans) 
				continue ;
		}
		else {
			dfs[v] = dfs[u] + get(tim,be) + en;
			ans = min(ans,dfs[v]);
			continue;
		}
		dfss(v,en);
	}
}

int main(){
	//freopen("txt.in","r",stdin);
	n = fr(),m = fr(),A = fr(),B = fr(),C = fr();
	int a,b,be,en;
	for (int i = 1; i <= m; i ++) { // 输入
		a = fr(),b = fr(),be = fr(),en = fr();
		e[a].push_back({b,be,en});
	}
	for (int i = 2; i <= n; i ++) { // 初始化
		dfs[i] = 2e9;
	}
	dfss(1,0);
	fw(ans);
	return 0;
}

2023/5/18 15:55
加载中...