代码

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

static inline void upd(ll& x, const ll y) {
    if (y > x)
        x = y;
}

static int n, m, c[5002];
struct Edge {
    char u, v, w;
} e[50002];
struct Event {
    int t, x, y;
    bool operator <(const Event& rhs) const {
        return t < rhs.t;
    }
} q[20005];
static ll pool[23333][1005];
static ll (*buf)[1005] = &pool[0];
static int xjj;
struct Pre {
    ll (*dp)[1005];
    int orig, anot; ll dx;
    void init(int s) {
        dp = buf;
        memset(dp, 0xcc, sizeof(*dp) * 5);
        dp[0][s] = 0;
        vector<ull> hs;
        for (int i = 0;; i++) {
            for (int j = 0; j < n; j++)
                dp[i][j] += c[j];
            ull h = 0;
            for (int j = 0; j < n; j++)
                h ^= (j + 1) * (ull) (dp[i][j] - dp[i][s]);
            hs.push_back(h);

            if (xjj) {
                if (i > xjj + 5 && !memcmp(hs.data() + i - xjj - 5, hs.data() + i - 5, 5 * sizeof(ull))) {
                    orig = i - xjj;
                    anot = i;
                    break;
                }
            } else {
                for (int j = 5; j + 5 < i; j++)
                    if (!memcmp(hs.data() + i - 5, hs.data() + j - 5, 5 * sizeof(ull))) {
                        orig = j;
                        anot = i;
                        goto ok;
                    }
            }

            memset(dp + i + 5, 0xcc, sizeof(*dp));
            for (int j = 0; j < m; j++)
                upd(dp[i + e[j].w][e[j].v], dp[i][e[j].u]);
        }
        ok:;
        dx = dp[anot][s] - dp[orig][s];
        xjj = anot - orig;
        buf += anot;
    }
    ll query(int T, int t) {
        if (T < anot)
            return dp[T][t];
        return dp[orig + (T - orig) % xjj][t] + (T - orig) / xjj * dx;
    }
} pre[50002];

static ll calc(int s, int t, int T) {
    return pre[s].query(T, t) - c[t];
}

int main() {
    int T, k;
    cin >> n >> m >> T >> k;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i].u = u - 1; e[i].v = v - 1; e[i].w = w;
    }

    for (int i = 0; i < n; i++)
        pre[i].init(i);

    for (int i = 1; i <= k; i++) {
        cin >> q[i].t >> q[i].x >> q[i].y;
        q[i].x--;
    }
    sort(q + 1, q + k + 1);
    q[0].t = 0; q[0].x = 0; q[0].y = 0;
    q[k + 1].t = T; q[k + 1].x = 0; q[k + 1].y = c[0];

    static ll dp[200005];
    memset(dp, 0xcc, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= k + 1; i++) {
        for (int j = 0; j < i; j++)
            upd(dp[i], dp[j] + calc(q[j].x, q[i].x, q[i].t - q[j].t));
        dp[i] += q[i].y;
    }
    upd(dp[k + 1], -1);
    cout << dp[k + 1] << endl;

    return 0;
}

评测结果