NOI 2020 美食家题解：拆点 + Max-Plus 矩阵快速幂 + 倍增优化

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

typedef long long ll;
const ll INF = 4e18; // 注意防溢出，用正数 INF 配合负号

int n, m, T, k;
int S; // 矩阵大小 5n

// 获取拆点后的 ID
// 点下标从 1 开始，附加状态 c 范围 [0, 4]
int get_id(int u, int c) {
    return (u - 1) + c * n + 1;
}

struct Matrix {
    ll mat[255][255];
    Matrix() {
        for(int i=1; i<=S; i++)
            for(int j=1; j<=S; j++)
                mat[i][j] = -INF;
    }
} base[35]; // base[p] 存 M^{2^p}

// 矩阵乘矩阵 (O(S^3))
Matrix mul(Matrix A, Matrix B) {
    Matrix res;
    for(int k_idx=1; k_idx<=S; k_idx++) {
        for(int i=1; i<=S; i++) {
            if(A.mat[i][k_idx] == -INF) continue;
            for(int j=1; j<=S; j++) {
                if(B.mat[k_idx][j] == -INF) continue;
                res.mat[i][j] = max(res.mat[i][j], A.mat[i][k_idx] + B.mat[k_idx][j]);
            }
        }
    }
    return res;
}

struct Vector {
    ll v[255];
    Vector() {
        for(int i=1; i<=S; i++) v[i] = -INF;
    }
};

// 向量乘矩阵 (O(S^2)) 满分关键！
Vector mul_vec(Vector A, Matrix B) {
    Vector res;
    for(int j=1; j<=S; j++) {
        for(int i=1; i<=S; i++) {
            if(A.v[i] != -INF && B.mat[i][j] != -INF) {
                res.v[j] = max(res.v[j], A.v[i] + B.mat[i][j]);
            }
        }
    }
    return res;
}

struct Event {
    int t, x;
    ll y;
    bool operator<(const Event& rhs) const {
        return t < rhs.t;
    }
} ev[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> T >> k;
    S = 5 * n;
  
    vector<ll> c(n + 1);
    for(int i=1; i<=n; i++) cin >> c[i];

    // 初始化转移矩阵
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=4; j++) {
            // (i, j) -> (i, j-1) 权值为 0
            base[0].mat[get_id(i, j)][get_id(i, j-1)] = 0;
        }
    }

    for(int i=1; i<=m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // (u, 0) -> (v, w-1) 权值为 c[v]
        base[0].mat[get_id(u, 0)][get_id(v, w-1)] = c[v];
    }

    // 预处理倍增矩阵
    for(int p=1; p<=30; p++) {
        base[p] = mul(base[p-1], base[p-1]);
    }

    for(int i=1; i<=k; i++) {
        cin >> ev[i].t >> ev[i].x >> ev[i].y;
    }
    sort(ev + 1, ev + 1 + k);

    // 初始状态
    Vector V;
    V.v[get_id(1, 0)] = c[1];
  
    int cur_time = 0;
    for(int i=1; i<=k; i++) {
        int dt = ev[i].t - cur_time;
        if (dt < 0) continue; // 忽略无效事件
      
        // 用向量乘法跳跃 dt 步
        for(int p=30; p>=0; p--) {
            if((dt >> p) & 1) {
                V = mul_vec(V, base[p]);
            }
        }
      
        cur_time = ev[i].t;
        // 加上美食节的奖励
        if (V.v[get_id(ev[i].x, 0)] != -INF) {
            V.v[get_id(ev[i].x, 0)] += ev[i].y;
        }
    }

    // 处理最后一个事件到 T 的剩余时间
    if (cur_time < T) {
        int dt = T - cur_time;
        for(int p=30; p>=0; p--) {
            if((dt >> p) & 1) {
                V = mul_vec(V, base[p]);
            }
        }
    }

    if(V.v[get_id(1, 0)] < 0) {
        cout << -1 << "\n";
    } else {
        cout << V.v[get_id(1, 0)] << "\n";
    }

    return 0;
}