链接题目大意有n个点m条边每个点有个权值c每条边有长度w要求刚好走过长度总共为T的路可重复从1号点回到1号点最大化选择路径上每个点的权值的总和。其中还有k个在刚好走过t的长度时在点u会有额外的权值v。思路很容易想到状态为f i u f_{i \ u}fiu​的转移表示走过i长度时刚好在点u的最大权值但时间复杂度显然不够。假设k0考虑矩阵加速优化原来的转移方程f i v m a x ( f i − w u c v ) f_{i \ v} max(f_{i - w \ u} c_v)fiv​max(fi−wu​cv​)这里使用一个巧妙地思路将每个点u拆成5个点w的最大值u i u_iui​向u i 1 u_{i1}ui1​连一条边权为0的边对于原图的每条边从u w u_wuw​向v 1 v_1v1​连一条边权为c的边这样可以保证每次不能停在原地且巧妙地将c融入矩阵之中方便后续的乘法操作。n * 5然后根据转移方程这里的矩阵加速就是c i j m a x ( a i k b k j ) c_{i \ j} max(a_{i \ k} b_{k \ j})cij​max(aik​bkj​)用矩阵快快速幂实现。k不等于0相当于将从0到T的一整次矩阵快速幂分成k次来做每次只需要在中断处将额外权值加入ans就可以。这里还需要一个优化。先将矩阵指数幂预处理出来。每次从last-now的长度时将now-last进行指数分解2 a 2 b … … 2^a2^b……2a2b……每次只需要从预处理出的指数幂中拿出矩阵进行ans更新不需要log(now - last在算一次。时间复杂度O ( l o g T ( 5 n ) 3 k l o g T ( 5 n ) 2 ) O(log \ T \ (5n)^3 k \ log \ T \ (5n)^2)O(logT(5n)3klogT(5n)2)code#includeiostream#includecstdio#includealgorithm#definelllonglongusingnamespacestd;constll MAXN505,inf1e16;ll n,m,T,k;ll C[MAXN],a[MAXN][MAXN],ans[MAXN],b[MAXN];ll Pow[31][MAXN][MAXN];structReward{ll t,u,v;}t[MAXN];boolcmp(Reward x,Reward y){returnx.ty.t;}voidmul_(ll to,ll fro){for(ll i1;in;i)for(ll j1;jn;j){Pow[to][i][j]-inf;for(ll k1;kn;k)Pow[to][i][j]max(Pow[to][i][j],Pow[fro][i][k]Pow[fro][k][j]);}}voidmul_ans(ll cnt){for(ll i1;in;i)b[i]ans[i],ans[i]-inf;for(ll j1;jn;j)for(ll k1;kn;k)ans[j]max(ans[j],b[k]Pow[cnt][k][j]);}voidinit_(){for(ll i1;in;i)for(ll j1;jn;j)Pow[0][i][j]a[i][j];for(ll i1;i30;i)mul_(i,i-1);}voidUpdate(ll B){ll j30;while(B){if(B(1j))mul_ans(j),B-1j;j--;}}intmain(){scanf(%lld%lld%lld%lld,n,m,T,k);for(ll i1;in;i)scanf(%lld,C[i]);n*5;for(ll i1;in;i)for(ll j1;jn;j)a[i][j]ans[i]-inf;for(ll i1;in/5;i)for(ll j1;j5;j)a[(i-1)*5j][(i-1)*5j1]0;for(ll i1;im;i){ll u,v,w;scanf(%lld%lld%lld,u,v,w);a[(u-1)*5w][(v-1)*51]C[v];}init_();for(ll i1;ik;i)scanf(%lld%lld%lld,t[i].t,t[i].u,t[i].v);sort(t1,t1k,cmp);ans[1]C[1];for(ll i1;ik;i){ll Bt[i].t-t[i-1].t;Update(B);ans[(t[i].u-1)*51]t[i].v;}if(t[k].t!T)Update(T-t[k].t);if(ans[1]0)printf(-1);elseprintf(%lld,ans[1]);return0;}