代码

#include<bits/stdc++.h> 
using namespace std;

namespace my{

typedef long long LL;

const int N = 260;
LL A[31][N][N];
int n,m,T,K,val[N];

struct cbt{
	int t,u,v;
}ts[N];

bool cmp(cbt a,cbt b){
	return a.t < b.t;
}

int get(int t,int x){
	return t * n + x - 1;
}

void gma(LL &x,LL y) {x < y ? x = y : 0;}

signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m>>T>>K;
	for(int i = 1;i<=n;i++) cin>>val[i];
	memset(A,0xcf,sizeof(A));
	for(int i= 1;i<=m;i++) {
		int b,e,w;
		cin>>b>>e>>w;
		A[0][get(4,e)][get(5 - w,b)] = val[e];
	}
	for(int i = 0;i<4;i++) 
		for(int j = 1;j<=n;j++) 
			A[0][get(i,j)][get(i + 1,j)] = 0;
	const int lim = n * 5;
	for(int i = 0;i!=30;i++) 
		for(int j = 0;j<lim;j++) 
			for(int k = 0;k<lim;k++)
				for(int l = 0;l<lim;l++) 
					gma(A[i+1][j][l],A[i][j][k] + A[i][k][l]);
	
	static LL dp[2][N];
	memset(dp,0xcf,sizeof(dp));
	int now = 0,lst = 1;
	dp[now][get(4,1)] = val[1];
	auto trans = [&](int dt){
		for(int j = 0;j!=31;j++) {
			if(dt >> j & 1) {
				swap(now,lst);
				memset(dp[now],0xcf,sizeof(dp[now]));
				for(int k = 0;k<lim;k++) 
					for(int l = 0;l<lim;l++) 
						gma(dp[now][k],dp[lst][l] + A[j][k][l]);
			}
		}
	};
	
	for(int i = 1;i<=K;i++) cin>>ts[i].t>>ts[i].u>>ts[i].v;
	sort(ts+1,ts + K + 1,cmp);
	for(int i = 1;i<=K;i++) {
		int dt = ts[i].t - ts[i-1].t;
		trans(dt);
		dp[now][get(4,ts[i].u)] += ts[i].v;
	}
	trans(T - ts[K].t);
	LL ans = dp[now][get(4,1)];
	if(ans < 0) ans = -1;
	cout<<ans<<'\n';

	return 0;
}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	return my::main();
}

评测结果