Luogu

LOJ

分析

如果见得多的话，从 “恰好第 $T$ 天回到城市 $1$”、$n\leq 50$、$w_i\leq 5$ 和 $T\leq 10^9$ 中不难知道本题要用矩阵快速幂。

这类问题是这样的：边有边权，求从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长路。

对这种题可以想到 DP。设 $dp_{k,i,j}$ 表示从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长路，$G$ 为邻接矩阵，则有转移

$$dp_{k,i,j}=\max_p\left\{dp_{k-1,i,p}+G_{p,j}\right\}$$

定义一个广义矩阵乘法

$$C_{i,j}=\max_{k}\left\{A_{i,k}+B_{k,j}\right\}$$

把 $dp_k$ 看成矩阵，则上式可以改写为

$$dp_k=dp_{k-1}\times G$$

因为这个广义矩阵乘法满足结合律（证明留给读者作为练习），所以有

$$dp_k=dp_0\times G^k$$

这样子就可以做到 $\mathcal{O}(n^3\log k)$。

然而本题和上面这个东西差的有点远，考虑如何转化过去。

首先，本题中是点权而不是边权。于是我们把每个点的点权作为它所有入边的边权，再特判起始点的点权（即把 $dp_{0,1,1}$ 设成 $c_1$）即可。

其次，本题中每条边不是当 $1$ 条边而是当 $w_i$ 条边算的。因为 $w_i$ 很小，所以考虑把边 $e$ 拆成若干个点 $e_i$ 表示在这条边上的第 $i$ 天。这样子对于原图中一条边 $e=(u,v,w)$，我们可以拆成 $(u,e_1,0),(e_1,e_2,0),\cdots,(e_{w-2},e_{w-1},0),(e_{w-1},v,c_v)$（$w=1$ 时是 $(u,v,c_v)$）。

最后，本题中还有 $k$ 个美食节。我们只需要在时间相邻的两个美食节间乘 $G$ 转移，然后在美食节那一天乘一个举办城市入边边权加上了 $y$ 的邻接矩阵转移即可。

这样子就成功转化成了上面的模型 …… 等等，这个点数是 $n+4m$ 的 /jk

冷静分析一下可以发现我们并没有必要拆边，而是可以直接拆点。对于从 $u$ 花 $w$ 天走到 $v$ 这个过程，我们可以看成在 $u$ 待了 $w-1$ 天且只在第一天获得点权，然后在第 $w$ 天到达 $v$。这样子对于每个点 $u$ 拆成若干个点 $u_i$ 表示在 $u$ 待的第 $i$ 天即可，连边类似。这样子点数就是 $5n$ 的了。

如果朴素地实现复杂度是 $\mathcal{O}((5n)^3k\log t)$ 的，显然过不去。因为我们只需要知道 $dp_{T,1,1}$，所以我们只需要保留 $dp_k$ 的第一行，再预处理 $G$ 的 $2^k$ 次幂即可做到 $\mathcal{O}((5n)^3\log T+(5n)^2k\log T)$。

代码

考场代码，可能写得有点丑，还请见谅。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X;
}

const int N=250+10,K=200+10;

int n,m,T,k,c[N];
int id[N][6],tot;

struct festival { int t,x,y; } t[K];
bool operator <(festival a,festival b) { return a.t<b.t; }

struct Matrix {
    ll s[N][N];
    Matrix() { memset(s,0xc0,sizeof(s)); }
    ll* operator [](int i) { return s[i]; }
} Q[31];
ll A[N];
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int i=1;i<=tot;++i)
        for (int k=1;k<=tot;++k) {
            if (a[i][k]<0) continue;
            for (int j=1;j<=tot;++j)
                c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        }
    return c;
}
void Mul(Matrix Q) {
    static ll B[N];
    for (int i=1;i<=tot;++i) B[i]=-4e18;
    for (int k=1;k<=tot;++k) {
        if (A[k]<0) continue;
        for (int j=1;j<=tot;++j)
            B[j]=max(B[j],A[k]+Q[k][j]);
    }
    for (int i=1;i<=tot;++i) A[i]=B[i];
}

int main() {
    tot=n=read(),m=read(),T=read(),k=read();
    for (int i=1;i<=n;++i) c[i]=read();
    for (int i=1;i<=n;++i) id[i][0]=i;
    for (int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        for (int j=1;j<w;++j) if (!id[u][j]) id[u][j]=++tot;
        for (int j=1;j<w;++j) Q[0][id[u][j-1]][id[u][j]]=0;
        Q[0][id[u][w-1]][v]=c[v];
    }
    for (int i=1;i<=k;++i) t[i]=(festival){read(),read(),read()};
    sort(t+1,t+k+1); t[0]=(festival){0,0,0},t[k+1]=(festival){T,0,0};
    for (int i=1;i<=30;++i) Q[i]=Q[i-1]*Q[i-1];
    for (int i=2;i<=tot;++i) A[i]=-4e18; A[1]=c[1];
    for (int i=1;i<=k+1;++i) {
        int dt=t[i].t-t[i-1].t;
        for (int j=30;~j;--j) if (dt&(1<<j)) Mul(Q[j]);
        A[t[i].x]+=t[i].y;
    }
    if (A[1]<0) puts("-1");
    else printf("%lld\n",A[1]);
    return 0;
}