不是正解,但不知道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;
}