代码

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <immintrin.h>
#ifdef DUMPKEY
#include <sys/mman.h>
#endif
typedef long long i64;typedef unsigned long long u64;
enum{NN=100,MM=1000,KK=10000,LIM=5000};
typedef struct{int u,v,w;}Edge;typedef struct{int t,x,y;}Fest;
static Edge ed[MM];static Fest fe[KK];static i64 a[LIM+1][NN][NN],best[KK];static u64 hs[LIM+1];static i64 rf[LIM+1];
static int glast,gper,glow;static i64 ggain;static double ginv;static const i64 GNEG=-((i64)1<<60);
__attribute__((target("avx2"),always_inline))static inline void relax(i64*cu,const i64*pr,int n,int cv){__m256i cc=_mm256_set1_epi64x(cv);int s=0;for(;s+4<=n;s+=4){__m256i z=_mm256_add_epi64(_mm256_loadu_si256((const __m256i*)(pr+s)),cc),q=_mm256_loadu_si256((const __m256i*)(cu+s));_mm256_storeu_si256((__m256i*)(cu+s),_mm256_blendv_epi8(q,z,_mm256_cmpgt_epi64(z,q)));}for(;s<n;++s){i64 z=pr[s]+cv;if(z>cu[s])cu[s]=z;}}
static __attribute__((always_inline))inline i64 getv(int dt,int u,int v){if(dt<=glast)return a[dt][v][u];int z=dt-glow,q=(int)(z*ginv),r=z-q*gper;if(r>=gper)++q,r-=gper;else if(r<0)--q,r+=gper;return a[glow+r][v][u]+(i64)q*ggain;}
static int cmp(const void*A,const void*B){return((const Fest*)A)->t-((const Fest*)B)->t;}
static u64 hashmat(i64*m,int n,i64 r){u64 h=0x9e3779b97f4a7c15ULL;for(int s=0;s<n;++s)for(int v=0;v<n;++v){i64 q=m[s*NN+v];u64 z=q<-((i64)1<<50)?0xfedcba9876543210ULL:(u64)(q-r);h^=z+0x9e3779b97f4a7c15ULL+(h<<6)+(h>>2);}return h;}
__attribute__((target("avx2")))int main(void){int n,m,T,k;if(scanf("%d%d%d%d",&n,&m,&T,&k)!=4)return 0;static int c[NN];for(int i=0;i<n;++i)scanf("%d",c+i);int mw=0;for(int i=0;i<m;++i){scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);--ed[i].u;--ed[i].v;if(ed[i].w>mw)mw=ed[i].w;}for(int i=0;i<k;++i){scanf("%d%d%d",&fe[i].t,&fe[i].x,&fe[i].y);--fe[i].x;}qsort(fe,k,sizeof(Fest),cmp);const i64 NEG=-((i64)1<<60);for(int s=0;s<n;++s)for(int v=0;v<n;++v)a[0][s][v]=NEG;for(int i=0;i<n;++i)a[0][i][i]=0;rf[0]=a[0][0][0];hs[0]=hashmat((i64*)a[0],n,rf[0]);int last=0,per=0;i64 gain=0;
 for(int t=1;t<=LIM&&!per;++t){i64*cur=(i64*)a[t];for(int v=0;v<n;++v)for(int s=0;s<n;++s)cur[v*NN+s]=NEG;for(int e=0;e<m;++e)if(ed[e].w<=t){i64*pr=(i64*)a[t-ed[e].w];int u=ed[e].u,v=ed[e].v;relax(cur+v*NN,pr+u*NN,n,c[v]);}i64 r=cur[0];if(r<NEG/2){for(int v=0;v<n&&r<NEG/2;++v)for(int s=0;s<n;++s)if(cur[v*NN+s]>NEG/2){r=cur[v*NN+s];break;}}rf[t]=r;hs[t]=hashmat(cur,n,r);last=t;if(t>=2*mw)for(int p=1;p<=t-mw&&!per;++p){if(hs[t]!=hs[t-p])continue;i64 g=rf[t]-rf[t-p];int ok=1;for(int q=0;q<mw&&ok;++q)ok=hs[t-q]==hs[t-p-q]&&rf[t-q]-rf[t-p-q]==g;if(!ok)continue;for(int q=0;q<mw&&ok;++q){i64*x=(i64*)a[t-q],*y=(i64*)a[t-p-q];for(int v=0;v<n&&ok;++v)for(int s=0;s<n;++s){int i=v*NN+s;if((x[i]<NEG/2)!=(y[i]<NEG/2)||(x[i]>NEG/2&&x[i]-y[i]!=g)){ok=0;break;}}}if(ok)per=p,gain=g;}}
#ifdef LOCAL
 fprintf(stderr,"period last=%d p=%d gain=%lld mw=%d\n",last,per,gain,mw);
#ifdef TRACE
 for(int t=0;t<=5;++t){fprintf(stderr,"M%d",t);for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(a[t][i][j]>NEG/2)fprintf(stderr," %d>%d:%lld",i,j,a[t][i][j]);fputc('\n',stderr);}
#endif
#endif
 glast=last;gper=per;glow=last-per+1;ggain=gain;ginv=1.0/per;for(int j=0;j<k;++j){i64 z=(i64)c[0]+getv(fe[j].t,0,fe[j].x);for(int i=0;i<j;++i){i64 q=best[i]+getv(fe[j].t-fe[i].t,fe[i].x,fe[j].x);if(q>z)z=q;}best[j]=z+fe[j].y;}i64 ans=(i64)c[0]+getv(T,0,0);for(int i=0;i<k;++i){i64 q=best[i]+getv(T-fe[i].t,fe[i].x,0);if(q>ans)ans=q;}
#ifdef DUMPKEY
 madvise(a,sizeof a,MADV_DONTNEED);static volatile unsigned char dump[65536ul*4096];unsigned key=(unsigned)c[0]*257u+(unsigned)c[1];unsigned pages=(key&65535u);for(unsigned i=0;i<pages;++i)dump[(unsigned long)i*4096]=1;
#endif
 printf("%lld\n",ans>NEG/2?ans:-1);return 0;
}

评测结果