原题链接：https://www.luogu.com.cn/problem/P6772

题意解读：图中边权表示天数，点权表示受益，另外在不同的时间不同的点举办美食节，使得经过该点获得额外收益，求从1点T天后回到1点的最大收益。

解题思路：

由于T取值10^9，常规的DP即便O(n)级别也是不可行的，必须log(n)的复杂度才能解决，可以推测如果该DP问题能转化成矩阵快速幂，就可能达成该目的。

矩阵快速幂与路径问题有两个重要的定理，有必要介绍一下，这里只说结论，不加证明：

1、两点间只经过n条边的总路径数量

用邻接矩阵M表示一个图，M(i,j)为其第i行第j列元素，表示点i和点j的连接关系，如果点i和点j直连，则M(i,j)=1，否则M(i,j)=0。另外，当i=j时，M(i,j)=0。

定理1：计算邻接矩阵的幂G=M^n，其元素G(i,j)的值表示从点i到点j经过n条边的总路径数量。

2、两点间只经过n条边的最短（最长）路径长度

用邻接矩阵M表示一个图，M(i,j)为其第i行第j列元素，表示点i和点j的连接关系，如果点i和点j直连，设M(i,j)表示边ij的权值，否则等于∞（最长路用-∞），

当i=j时，M(i,j)=∞（最长路用-∞）。

定义矩阵的广义乘法：M * M = mink=1~N (M(i, a) + M(a, j)) （最长路用max），也就是把普通的矩阵乘法从求和改成了取最小值，内部相乘改成了相加。

定理2：计算邻接矩阵的广义幂G = M^n，G(i,j)的值是从i到j经过n条边的最短（最长）路径长度。

ok，有了以上定理2，看这道题如何转化到这个模型。

技巧1：拆点

我们知道，两点之间路径长度是w，w取值1~5,而以上路径模型每次乘法代表走一步，可以将原图进行拆点：一个点拆成5个点

如#1点拆成5->4->3->2->1，g[5][4]=g[4][3]=g[3][2]=0, g[2][1]=w[1]，w[1]是#1的收益

2点拆成10->9->8->7->6，g[10][9]=g[9][8]=g[8][7]=0, g[7][6]=w[2]，w[2]是#2的收益

如果2到1之间有权值3的边，那么应该建立g[6][3]=0，因为6是#2点的目标，6到1之间要经过3条边。

这样一来，原图转化成拆点之后的图，原来的问题就转化为求从1到1经过T条边的最长路。就和上述定理2的模型匹配上了。

技巧2：分段矩阵快速幂

由于存在美食节，一个特定的时间点会给特定的节点增加收益，可以将美食节按时间排序，最后补上一个时间T，K个美食节按时间分割成K+1段，

针对每一段的时间t，对答案乘上g^t，然后将该段美食节对x点的收益加到答案中，最终可以得到结果。

技巧3：预处理+二进制拆分

由于矩阵快速幂的时间复杂度为logT*n^3，n拆点后大概是250，分段做还是会导致超时。

可以提前将g2^i预处理出来，在计算分段矩阵快速幂是，对幂进行二进制拆分，然后用预处理的结果代替实时计算。

技巧4：答案矩阵相乘时的优化

由于答案只关心g[1][…]相关的结果，因此在做矩阵广义乘法时，不需要三层循环，只需要两层循环，对于行固定1即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 255, K = 205;
int n, m, T, k;

struct Matrix
{
    LL a[N][N]; //矩阵元素

    Matrix()
    {
        memset(a, -0x3f, sizeof(a)); //初始化为无穷小
    }

    Matrix operator*(const Matrix &to) const  //广义矩阵乘法
    {
        Matrix res;
        for(int i = 1; i <= n * 5; i++)
            for(int j = 1; j <= n * 5; j++)
                for(int k = 1; k <= n * 5; k++)
                    res.a[i][j] = max(res.a[i][j], a[i][k] + to.a[k][j]);
        return res;
    }

    Matrix operator&(const Matrix &to) const  //广义矩阵乘法，但只考虑从1到j的路径
    {
        Matrix res;
        for(int j = 1; j <= n * 5; j++)
            for(int k = 1; k <= n * 5; k++)
                if(a[1][k] >= 0 && to.a[k][j] >= 0) //1到k有路径且k到j有路径
                    res.a[1][j] = max(res.a[1][j], a[1][k] + to.a[k][j]);
        return res;
    }
} base, tmp[35], ans; //base是基础矩阵保存图，tmp用于存储2^i幂矩阵，ans用于存储答案

struct Fes 
{
    int t; //时间
    int pos; //节点
    int add; //额外愉悦值
    bool operator<(const Fes &x) const 
    {
        return t < x.t; //按时间升序
    }
} fes[K]; //美食节

int c[N]; //愉悦值

int main()
{
    cin >> n >> m >> T >> k;
    for(int i = 1; i <= n; i++) cin >> c[i]; //输入愉悦值

    //拆点：1拆5
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= 4; j++)
        {
            int a = (i - 1) * 5 + j + 1; //拆点编号
            int b = (i - 1) * 5 + j; //拆点编号
            if(j == 1) base.a[a][b] = c[i]; //连边愉悦值为w[i]
            else base.a[a][b] = 0; //其他边愉悦值为0
        }
    }

    //建边
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w; //输入边
        //拆点连边
        int a = (u - 1) * 5 + 1; //u的拆点编号
        int b = (v - 1) * 5 + w; //v的拆点编号,这样a走到b需要经过w条边
        if(w == 1) base.a[a][b] = c[v]; //直连边愉悦值为c[v]
        else base.a[a][b] = 0; //非直连边愉悦值为0，因为经过v拆点最后一条边或得到愉悦值
    }

    //输入美食节
    for(int i = 1; i <= k; i++) cin >> fes[i].t >> fes[i].pos >> fes[i].add;
    sort(fes + 1, fes + k + 1); //按时间升序排序

    //预处理base的2^i幂矩阵
    tmp[0] = base; //2^0幂矩阵就是base
    for(int i = 1; i < 35; i++)
        tmp[i] = tmp[i - 1] * tmp[i - 1]; //快速幂预处理

    //答案初始化为单位矩阵
    ans.a[1][1] = 0;

    //处理美食节
    fes[++k].t = T; //添加一个虚拟美食节，时间为T，位置为0，愉悦值为0
    int begin = 1; //当前美食节区间开始时间
    for(int i = 1; i <= k; i++)
    {
        int end = fes[i].t; //当前美食节的时间
        int time = end - begin + 1; //当前区间的时间长度
        for(int j = 0; j <= 31; j++)
        {
            if(time & (1 << j)) //如果当前时间长度的二进制第j位为1
            {
                ans = ans & tmp[j]; //将答案与2^j幂矩阵相乘
            }
        }
        begin = end + 1; //更新区间开始时间
        //处理当前美食节
        int pos = (fes[i].pos - 1) * 5 + 1; //美食节位置对应的拆点编号
        for(int j = 1; j <= n * 5; j++)
        {
            if(ans.a[j][pos] >= 0) //如果从j到pos有路径
            {
                ans.a[j][pos] += fes[i].add; //增加愉悦值
            }
        }
    }

    //输出答案
    if(ans.a[1][1] < 0) //如果从1到1没有路径
    {
        cout << -1; //输出不可能
    }
    else
    {
        cout << ans.a[1][1] + c[1]; //输出从1到1的最大愉悦值,加上起点的愉悦值
    }

    return 0;
}