代码

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

const int MAXN = 100;
const int MAXM = 1000;
const int MAXW = 100;
const int MAXK = 10002;

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

static int n, m, c[MAXN];
struct Edge {
    char u, v, w;
} e[MAXM];
struct Event {
    int t, x, y;
    bool operator <(const Event& rhs) const {
        return t < rhs.t;
    }
} q[MAXK];
static ll pool[500000][MAXN];
static ll (*buf)[MAXN] = &pool[0];
static int xjj;
struct Pre {
    ll (*dp)[MAXN];
    int orig, anot; ll dx;
    void init(int s) {
        dp = buf;
        memset(dp, 0xcc, sizeof(*dp) * MAXW);
        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 + MAXW && !memcmp(hs.data() + i - xjj - MAXW, hs.data() + i - MAXW, MAXW * sizeof(ull))) {
                    orig = i - xjj;
                    anot = i;
                    break;
                }
            } else {
                for (int j = MAXW; j + MAXW < i; j++)
                    if (!memcmp(hs.data() + i - MAXW, hs.data() + j - MAXW, MAXW * sizeof(ull))) {
                        orig = j;
                        anot = i;
                        goto ok;
                    }
            }

            memset(dp + i + MAXW, 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;
        // fprintf(stderr, "pre %d, orig %d, anot %d, dx %lld\n", s, orig, anot, dx);
    }
    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[MAXN];

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

int main() {
// #ifdef ONLINE_JUDGE
//     freopen("delicacy.in", "r", stdin);
//     freopen("delicacy.out", "w", stdout);
// #endif
    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);
    
    cerr << "Loop length " << xjj << ", weight " << pre[0].dx << endl;

    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[MAXK];
    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;

    cerr << buf - pool << endl;

    return 0;
}

评测结果