代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m,k;

long long T;

int num,head[3100000];

long long v[31000];

struct query
{
  long long now,v;
  int p;
}q[100010];

struct M
{
  long long s[1010][1010],r,c;
  void clear()
  {
    for(int i=1;i<=300;i++) for(int j=1;j<=300;j++) s[i][j]=-0x3f3f3f3f3f3f3f3f;
  }
}ans,Ye[40];

M operator * (const M &x,const M &y)
{
  M now;
  now.clear();
  now.r=x.r;
  now.c=y.c;
  for(int k=1;k<=x.c;k++)
  {
    for(int i=1;i<=x.r;i++)
    {
      for(int j=1;j<=y.c;j++)
      {
        now.s[i][j]=max(now.s[i][j],x.s[i][k]+y.s[k][j]);
      }
    }
  }
  return now;
}

bool cmp(query a,query b)
{
  return a.now<b.now;
}

int main()
{
  scanf("%d%d%lld%d",&n,&m,&T,&k);
  ans.clear();
  ans.r=1;
  ans.c=n*5;
  ans.s[1][1]=0;
  Ye[0].clear();
  Ye[0].r=n*5;
  Ye[0].c=n*5;
  for(int i=1;i<=n*5;i++) if(i%5) Ye[0].s[i][i+1]=0;
  for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
  for(int i=1;i<=m;i++)
  {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    Ye[0].s[(a-1)*5+c][(b-1)*5+1]=v[b];
  }
  for(int i=1;i<=31;i++) Ye[i]=Ye[i-1]*Ye[i-1];
  for(int i=1;i<=k;i++) scanf("%lld%d%lld",&q[i].now,&q[i].p,&q[i].v);
  sort(q+1,q+k+1,cmp);
  q[0].now=0;
  for(int i=1;i<=k;i++)
  {
    for(int j=0;j<=31;j++) if((q[i].now-q[i-1].now-1)&(1ll<<j)) ans=ans*Ye[j];
    M wee=Ye[0];
    for(int j=1;j<=n*5;j++) if(wee.s[j][(q[i].p-1)*5+1]>=0) wee.s[j][(q[i].p-1)*5+1]+=q[i].v;
    ans=ans*wee;
  }
  for(int j=0;j<=31;j++) if((T-q[k].now)&(1ll<<j)) ans=ans*Ye[j];
  if(ans.s[1][1]>0) printf("%lld",ans.s[1][1]+v[1]);
  else puts("-1");
}

评测结果