本文共 1138 字，大约阅读时间需要 3 分钟。

前言

我考场（线上赛）切NOI的题了！

正题

题目链接:

题目大意

$n$个点$m$条边，每个城市有不同的愉悦值，从$1$出发，要求经过$T$的时间后回到点$1$(不能原地停留。

特别的是有$k$个美食节，在第$t_i$个时刻如果在第$x_i$个城市就可以额外获得$y_i$的愉悦值，求路径上最大愉悦值

解题思路

首先矩阵乘法变形后是可以求最长路的

之后之前有一道题目和这题很像，因为边权最大只有5，所以可以将每个点分成$5$个点就可以跑矩阵乘法了。这样有$250$个点，跑一次矩阵乘法是$O(250^3\log T)$，不考虑美食节的情况下可以过，但是如果有美食节时间复杂度就接近$O(k\ast 250^3\log T)$显然不可过。

然后之前有一道$NOIOnline$的题目正解是先预处理出$logT$个矩阵然后再用向量乘矩阵

我们就得出了解法，我们先预处理使得$F_i=A^{2^i}$，然后这样我们用向量乘矩阵就是$O(n^2)$的，之后每次做矩阵到每一个美食节，然后对于在那一天的情况加上一个愉悦值即可，可以通过本题。

时间复杂度$:O((nw{)}^3\log T+(nw{)}^{2}k\log T)$

$code$

#include
   
    #include
    
     #include
     
      #define p(x,y) ((x)*5+(y))#define ll long longusing namespace std;const ll N=51;struct matrix{
   	ll a[N*5][N*5];}f[32];struct node{
   	ll t,x,y;}h[210];ll n,m,T,k,tot,Size,a[N*5],p2[32],c[N*5];matrix operator*(const matrix &a,const matrix &b){
   	matrix c;memset(c.a,0xcf,sizeof(c.a));	for(ll i=0;i
     
    
   

转载地址：http://wcwaf.baihongyu.com/