题意分析
给出一个带权有向图，要求从节点 $1$ 出发，经过恰好 $T$ 的边权和，回到节点 $1$ ，求可经过的最大点权和。特别地，经过的边权和达到部分特殊数时，会有某个点的点权发生改变。
思路分析
朴素算法
- 时间复杂度： $O(mT)$
- 理论得分： $40pts$
设 $f_{i,j}$ 表示在节点 $j$ ，经过的边权和为 $i$ 时可经过的最大点权和。很容易可以得出 DP 方程：
$$f_{i,j}=max_{(x,j,w)in E}(f_{i-w,x})+c_j$$
暴力转移，点权改变的情况特判修改即可。
优化1
- 时间复杂度： $O(125n^3klog T)$
- 理论得分：$75pts$
可以发现 $w$ 的数据范围很小，想到用矩阵快速幂优化。
首先拆点，令所有边边权都为 $1$ ，然后将所求的点权转化为边权：设有 $(u,v,w)in E$ ，则可以将 $u$ 拆成 $u_0,u_1,...,u_{w-1}$ ，从 $u_{i-1}$ 向 $u_i$ 间连一条边，边权为 $0$ ，然后从 $u_{w-1}$ 向 $v$ 连一条边，边权为 $c_v$ 。
这样，问题就转化为，从节点 $1$ 出发，经过 $T$ 条边，回到节点 $1$ ，求可经过的最大边权和，即最长路。
定义一个广义矩阵乘法 $ans_{i,j}=max(a_{i,k}+b_{k,j})$ 。可以证明这个广义矩阵乘法同样满足矩阵乘法的基本运算律，如结合律。
设邻接矩阵为 $a$ ，可以很容易得出 DP 方程：
$$dp_i=dp_j*a^{i-j}$$
点权改变的情况怎么处理？只要先将时间从小到大排序，然后在相邻的时间之间转移，转移后在改变点权在邻接矩阵中的对应位置修改即可。
优化2
- 时间复杂度： $O(125n^3log T+25n^2klog T)$
- 理论得分： $100pts$
分析过后可以发现，因为要求的只是 $dp_{T_{1,1}}$ ，因此只要保留 $dp$ 矩阵的第一行即可；另外，发现在转移的时候要多次乘上邻接矩阵 $a$ 的相同次幂，因此可以先预处理出 $a$ 的 $2$ 的整数次幂。这样处理之后可以降低一维的复杂度。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=300;
const ll INF=0xcfcfcfcfcfcfcfcf;
struct Node
{
ll p[N][N];
}a[31];
struct Fes
{
int t,x,y;
#define t(i) b[i].t
#define x(i) b[i].x
#define y(i) b[i].y
}b[N];
int n,m,T,K;
int c[N],id[N][5];
ll dp[N];
Node Max(Node x)
{
Node now;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
now.p[i][j]=INF;
for(int k=1;k<=n;k++)
now.p[i][j]=max(now.p[i][j],x.p[i][k]+x.p[k][j]);
}
return now;
}//广义矩阵乘法
void Maxx(Node x)
{
ll now[N];
for(int i=1;i<=n;i++)
{
now[i]=INF;
for(int j=1;j<=n;j++)
now[i]=max(now[i],dp[j]+x.p[j][i]);
}
for(int i=1;i<=n;i++)
dp[i]=now[i];
}//一维乘二维
void pre()
{
for(int i=1;i<=30;i++)
a[i]=Max(a[i-1]);
}//预处理次幂
void fastpow(int x)
{
for(int i=30;i>=0;i--)
if(x&(1<<i))
Maxx(a[i]);
}//快速幂
bool cmp(Fes x,Fes y)
{
return x.t<y.t;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&T,&K);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]),id[i][0]=i;
memset(a,0xcfcf,sizeof(a));
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
for(int j=1;j<w;j++)
{
if(!id[u][j])
id[u][j]=++n;
a[0].p[id[u][j-1]][id[u][j]]=0;
}
a[0].p[id[u][w-1]][v]=c[v];//拆点
}
pre();
for(int i=1;i<=K;i++)
scanf("%d%d%d",&t(i),&x(i),&y(i));
sort(b+1,b+K+1,cmp);t(K+1)=T;
memset(dp,0xcfcf,sizeof(dp));dp[1]=c[1];//初状态
for(int i=1,d;i<=K+1;i++)
{
d=t(i)-t(i-1);
fastpow(d);
dp[x(i)]+=y(i);//点权改变
}//在相邻的时间之间转移
printf(dp[1]<0?"-1":"%lld",dp[1]);
return 0;
}