给你一张 \(n\) 个点 \(m\) 条边的有向图，经过每条边需要 \(w_i\) 的时间，每个点有价值 \(c_i\)。每次经过一个点时可以获得它的价值（可重复获得）。
还有 \(k\) 个附加价值 \((t, x, y)\) 表示如果你在 \(t\) 时刻恰好经过 \(x\)，那么会有 \(y\) 的附加价值。
求第 0 时刻从 1 出发，在 \(T\) 时刻回到 1 能获得的最大价值。
\(n\le 50, m \le 501, k \le 200, t_i \le T \le 10^9, 1 \le w_i \le 5\)
先考虑没有美食节的情况。
首先可以想到 dp。设 \(f_{u, i}\) 表示在第 \(i\) 个时刻到达节点 \(u\) 获得的最大价值。
转移就是枚举有向边 \((u, v, w)\)，\(f_{u, i} + c_v \rightarrow f_{v, i + w}\)。
考虑优化。由于第二维是 \(10^9\) 级别的，第一维很小，所以考虑矩阵快速幂优化。
先考虑把 \(i + w\) 变成 \(i + 1\) 的形式，这一步可以把一条长度为 \(w\) 的边拆成 \(w\) 条长度为 \(1\) 的边。这是点数是 \(n + 4m\) 的。
然后再考虑构造矩阵。可以构造一个 \((n + 4m) \times (n + 4m)\) 的矩阵 \(G\)，\(G_{i, j}\) 表示 \(i\) 走到 \(j\) 之后会获得的价值（也就是 \(c_j\)），如果没有边就设成 \(- \infty\)。初始的 dp 状态可以构造成 \(1 \times (n + 4m)\) 的矩阵 \(F\)，其中 \(F_{1, 0} = c_1\)，其他的都为 \(- \infty\)。
这样最终答案就变成了 \((F \times G^{T})_{1, 1}\)。
加上美食节就是把时间按美食节的时间分成若干块，块内矩阵快速幂转移，块间构造出包含美食节影响的矩阵再乘上进行转移。
时间复杂度 \(O((n + 4m)^3 k \log T)\)。
继续优化，可以发现块间乘的矩阵都是 \(G^{t}\) 的形式。由于向量乘矩阵是 \(O(n^2)\) 的，所以可以考虑预处理出 \(G^{2^i}\)，然后把 \(t\) 二进制拆分对应的乘一下就好了。时间复杂度 \(O((n + 4m)^3 \log T + (n + 4m)^2 k \log T)\)
可以发现，现在的问题在于点数太多了，所以考虑变拆边为拆点，就是把每个点 \(u\) 拆成 5 个点 \(u_0\)、\(u_1\)、\(u_2\)、\(u_3\)、\(u_4\) 分别表示到 \(u\) 后停留了 \(0\) 个单位的时间、到 \(u\) 后停留了 \(1\) 个单位的时间、到 \(u\) 后停留了 \(2\) 个单位的时间、到 \(u\) 后停留了 \(3\) 个单位的时间、到 \(u\) 后停留了 \(4\) 个单位的时间，这样如果有一条边 \((u, v, w)\)，那么我们只需要连一条 \(u_{w- 1} \rightarrow v_0\) 的边即可。这样点数就变成了 \(5n\) 的。
时间复杂度 \(O((5n)^3 \log T + (5n)^2 k \log T)\)。
constexpr int MAXN = 255, MAXLG = 30, MAXM = 5e2 + 9, MAXK = 2e2 + 9;
constexpr ll INF = 1e16;
int n, m, T, k, c[MAXN];
tuple<int, int, int> fes[MAXK];
struct Matrix {
int n, m;
ll mat[MAXN][MAXN];
Matrix(int _n = 0, int _m = 0): n(_n), m(_m) {
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
mat[i][j] = - INF;
return;
}
friend Matrix operator * (const Matrix &x, const Matrix &y) {
Matrix ans(x.n, y.m);
for (int i = 1; i <= ans.n; i ++)
for (int j = 1; j <= ans.m; j ++)
for (int k = 1; k <= x.m; k ++)
cmax(ans.mat[i][j], x.mat[i][k] + y.mat[k][j]);
return ans;
}
Matrix& operator *= (const Matrix &x) { return (*this) = (*this) * x; }
} G, pw[MAXLG], f;
void slv() {
n = Read<int>(), m = Read<int>(), T = Read<int>(), k = Read<int>();
auto get_id = [&](int u, int t) { return (u - 1) * 5 + t + 1; };
for (int i = 1; i <= n; i ++) c[i] = Read<int>();
G = Matrix(n * 5, n * 5);
for (int i = 1; i <= n; i ++)
for (int j = 0; j < 4; j ++)
G.mat[get_id(i, j)][get_id(i, j + 1)] = 0;
for (int i = 1; i <= m; i ++) {
int u = Read<int>(), v = Read<int>(), w = Read<int>();
G.mat[get_id(u, w - 1)][get_id(v, 0)] = c[v];
}
for (int i = 1; i <= k; i ++) {
int t = Read<int>(), x = Read<int>(), y = Read<int>();
fes[i] = make_tuple(t, x, y);
}
sort(fes + 1, fes + k + 1);
if (get<0>(fes[k]) != T) fes[++ k] = make_tuple(T, 1, 0);
pw[0] = G;
for (int i = 1; i <= __lg(T); i ++) pw[i] = pw[i - 1] * pw[i - 1];
f = Matrix(1, n * 5); f.mat[1][get_id(1, 0)] = c[1];
auto qpow = [&](Matrix &mat, int k) {
if (!k) return;
for (int i = 0; i <= __lg(k); i ++)
if (k >> i & 1) mat *= pw[i];
return;
};
for (int i = 1; i <= k; i ++) {
auto [t, x, y] = fes[i];
qpow(f, t - 1 - get<0>(fes[i - 1]));
Matrix F = G;
for (int j = 1; j <= n * 5; j ++)
F.mat[j][get_id(x, 0)] += y;
f *= F;
}
if (f.mat[1][1] < 0) f.mat[1][1] = -1;
Write(f.mat[1][1], '\n');
return;
}