求条

#include<bits/stdc++.h>
#define int long long
#define db double
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int inf=2e9;
const db eps=1e-7;
int n,m,T,k;
int O[265][265];
int F[35][265][265];
void cf(int p,int x[265][265],int y[265][265]){
	for(int i=1;i<=n*5+4;i++){
		for(int j=1;j<=n*5+4;j++){
			for(int k=1;k<=n*5+4;k++)if(y[i][k]>=0&&y[k][j]>=0)F[p][i][j]=max(F[p][i][j],y[i][k]+y[k][j]);
		}
	}
}
int ans[265];
int ccf(int a[265],int x[265][265]){
	int xx[265]={};
	memset(xx,-0x3f,sizeof(xx));
	for(int j=1;j<=n*5+4;j++)for(int k=1;k<=n*5+4;k++)if(a[k]>=0&&x[k][j]>=0)xx[j]=max(xx[j],a[k]+x[k][j]); 
	memcpy(ans,xx,sizeof(ans));
}
int dq[265];
struct WZOI{
	int t,x,y;
}msj[265];
bool cmp(WZOI x,WZOI y){
	return x.t<y.t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>T>>k;
	for(int i=1;i<=n;i++)cin>>dq[i];
	memset(O,-0x3f,sizeof(O));
	for(int i=1;i<=n;i++){
		O[i][n+(i-1)*4]=0;
		for(int j=1;j<=4;j++)O[n+(i-1)*4+j][n+(i-1)*4+j+1]=0;
	}
	memset(F,-0x3f,sizeof(F)); 
	while(m--){
		int x,y,w;
		cin>>x>>y>>w;
		O[(w==1?x:n+(x-1)*4+w-1)][y]=dq[y];
	}
	for(int i=1;i<=5*n+4;i++)for(int j=1;j<=5*n+4;j++)F[0][i][j]=O[i][j];
	for(int i=1;i<=log(T)/log(2)+1;i++)cf(i,F[i-1],F[i-1]);
	for(int i=1;i<=k;i++)cin>>msj[i].t>>msj[i].x>>msj[i].y;
	sort(msj+1,msj+k+1,cmp);
	msj[k+1].t=T; 
	for(int i=1;i<=k+1;i++){
		int l=msj[i].t-msj[i-1].t;
		int cnt=0;
		while(l){
			if(l&1)ccf(ans,F[cnt]);
			cnt++;
			l>>=1;
		}
		ans[msj[i].x]+=msj[i].y;
		
	}
	if(ans[1]<=0){
		cout<<-1;
		return 0;
	}
	cout<<ans[1]+dq[1];
	return 0;
}