代码

// cheat

#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;
}

评测结果