链接：
题目大意：
给定一个有 (n) 个节点的有向图，每一个点有点权，在某些时候达到某些点能获得额外值，从点 1 出发，问 (t) 天后回到点 1 的最大价值。
正文：
方法一：
直接无脑DP，设 (f_{i,j}) 表示第 (i) 天时正好到点 (j) 的最大价值，转移 (f_{i,j}=max{f_{i-w,k}}+c_j)
枚举时再加上附加值，时间复杂度 (O(Tm))。
代码：
f[0][1] = c[1];
for (int i = 1; i <= m; i++)
scanf ("%lld%lld%lld", &e[i].from, &e[i].to, &e[i].w);
for (ll i = 1, tim, u, v; i <= k; i++)
scanf ("%lld%lld%lld", &tim, &u, &v),TouShui[tim][u] = v;
for (int i = 1; i <= T; i++)
{
for (int j = 1; j <= m; j++)
if(f[i - e[j].w][e[j].from])
{
f[i][e[j].to] = max(f[i][e[j].to], f[i - e[j].w][e[j].from]) + c[e[j].to] + TouShui[i][e[j].to];
}
}
printf("%lld", f[T][1]);
方法二：
若附加值和边权先不管，这题就是矩阵乘法优化的神（S）怖（B）题，理由是不可能存在第某天在路上的情况。定义一个矩阵 (F_i) 表示到第 (i) 天的各个 (f_i) 的状态。那我们定义一个广义矩阵乘法 (C_{i,j}=max{B_{i,k}+C{k,j}})，那么构造一个邻接矩阵 (A)，(F_{i}=F_{i-1} imes A)，答案就是 (F_{t}=F_0 imes A^t) 了。只可惜这道题还有附加值和边权的问题。
边权问题：
注意看数据范围，发现边长小于等于五，直接拆点，建议不要拆边因为拆边数据过大会爆，如果你的程序过不了可能是因为拆的是边而不是点。
附加值问题：
可以给时间分段：
吃完一个美食节就直接跳到下一个美食节。最后再利用快速幂的思想给程序进行小优化就能过了。
代码：
最后提醒，检查数组范围，只要经过矩阵乘法运算的数组都要记得乘五（即拆点的范围）。
const int N = 60, M = 510, logT = 30, K = 210;
const ll inf = 4e17;
ll n, m, T, k, a[N * 5];
ll c[N * 5];
struct matrix
{
ll mat[N * 5][N * 5];
int n, m;
inline ll* operator [] (int b) { return mat[b];}
matrix() { memset(mat, 0xcf, sizeof mat);}
}F[logT + 5];
inline matrix operator * (matrix &a, matrix &b)
{
matrix c; c.n = a.n, c.m = b.m;
for (int k = 1; k <= a.m; k++)
for (int i = 1; i <= a.n; i++)
for (int j = 1; j <= b.m; j++)
c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
return c;
}
struct FoodFestival
{
ll t, x, y;
}fft[K];
bool cmp (FoodFestival x, FoodFestival y)
{
return x.t < y.t;
}
void mul(matrix &b)
{
memcpy(c, a, sizeof(c));
memset(a, 0xcf, sizeof(a));
for (int i = 1; i <= b.n; i++)
for (int j = 1; j <= b.m; j++)
a[j] = max(a[j], b[i][j] + c[i]);
return ;
}
void qpow(ll b)
{
for (ll i = 0; i <= logT; i++)
if(b & (1 << i)) mul(F[i]);
return;
}
signed main()
{
// freopen("delicacy.in", "r", stdin);
// freopen("delicacy.out", "w", stdout);
scanf ("%lld%lld%lld%lld", &n, &m, &T, &k);
F[0].n = F[0].m = n * 5;
for (int i = 1; i <= n; i++)
{
scanf("%lld", &c[i]);
for (int j = 1; j < 5; j++)
F[0][i + n * j][i + n * (j - 1)] = 0;
}
for (int i = 1; i <= m; i++)
{
ll u, v, tim;
scanf ("%lld%lld%lld", &u, &v, &tim);
F[0][u][v + n * (tim - 1)] = c[v];
}
for (int i = 1; i <= logT; i++)
F[i] = F[i - 1] * F[i - 1];
for (int i = 1; i <= k; i++)
scanf ("%lld%lld%lld", &fft[i].t, &fft[i].x, &fft[i].y);
sort (fft + 1, fft + 1 + k, cmp);
fft[++k] = (FoodFestival) {T, 0, 0};
memset (a, 0xcf, sizeof a);a[1] = c[1];
ll now = 0;
for (int i = 1; i <= k; i++)
{
qpow(fft[i].t - now);
a[fft[i].x] += fft[i].y;
now = fft[i].t;
}
if(a[1] < 0) puts("-1");
else printf("%lld
", a[1]);
return 0;
}