代码

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
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 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;}
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 s=0;s<n;++s)for(int v=0;v<n;++v)cur[s*NN+v]=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,cv=c[v];for(int s=0;s<n;++s){i64 z=pr[s*NN+u]+cv;if(z>cur[s*NN+v])cur[s*NN+v]=z;}}i64 r=cur[0];if(r<NEG/2){for(int s=0;s<n&&r<NEG/2;++s)for(int v=0;v<n;++v)if(cur[s*NN+v]>NEG/2){r=cur[s*NN+v];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 s=0;s<n&&ok;++s)for(int v=0;v<n;++v){int i=s*NN+v;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
#define GET(dt,u,v) ((dt)<=last?a[(dt)][(u)][(v)]:(per?(a[last-per+1+((dt)-(last-per+1))%per][(u)][(v)]+(i64)(((dt)-(last-per+1+((dt)-(last-per+1))%per))/per)*gain):NEG))
 for(int j=0;j<k;++j){i64 z=(i64)c[0]+GET(fe[j].t,0,fe[j].x);for(int i=0;i<j;++i){i64 q=best[i]+GET(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]+GET(T,0,0);for(int i=0;i<k;++i){i64 q=best[i]+GET(T-fe[i].t,fe[i].x,0);if(q>ans)ans=q;}printf("%lld\n",ans>NEG/2?ans:-1);return 0;
#undef GET
}

评测结果