题解

同步赛时看到\(m \leq 2\times 10 ^ 5, q_i \leq 1000\)的我灵光一闪，交了个\(\mathrm{O}(mt)\)的大暴力然后\(\mathrm{AC}\)此题

设\(f[i][j]\)表示当前在第\(i\)个站点，时刻为\(j\)的最小烦躁度，\(F(x) = Ax^2 + Bx + C\)。

然后枚举每一条边\(i\)，可以得到：\(f[y_i][j] = \min\{f[x_i][p_i] + F(j - q_i)\}\)。

直接\(\mathrm{DP}\)即可。

代码

#include 
    
     #include 
     
      inline int read(){    int data = 0, w = 1; char ch = getchar();    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();    if (ch == '-') w = -1, ch = getchar();    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();    return data * w;}const int maxn(1e5 + 10), maxm(2e5 + 10), T(1010), INF(0x3f3f3f3f);int n, m, A, B, C, maxQ, f[maxn][T];struct node { int x, y, p, q; } L[maxm];inline int operator < (const node &lhs, const node &rhs) { return lhs.q < rhs.q; }inline int F(int x) { return x * x * A + x * B + C; }void solve(){    for (int i = 1; i <= n; i++)        for (int j = 1; j <= maxQ; j++) f[i][j] = INF;    for (int j = 0; j <= maxQ; j++) f[1][j] = F(j);    for (int i = 1; i <= m; i++)    {        int x = L[i].y;        for (int j = L[i].q; j <= maxQ; j++)            f[x][j] = std::min(f[x][j], f[L[i].x][L[i].p] + F(j - L[i].q));    }    int ans = INF;    for (int j = 1; j <= maxQ; j++)        ans = std::min(ans, f[n][j] + j - C);    printf("%d\n", ans);}int main(){    n = read(), m = read(), A = read(), B = read(), C = read();    for (int i = 1; i <= m; i++) L[i] = (node) {read(), read(), read(), read()};    for (int i = 1; i <= m; i++) maxQ = std::max(maxQ, L[i].q);    std::sort(L + 1, L + m + 1), solve();    return 0;}