夏晓光(loveJY)的博客

这么简单的题就是因为没有练矩阵乘法啊QAQ

想当初矩阵乘法之王啊!

其实不难看出我们就是要求一个矩阵乘法,但是加权是有延时性的

所以我们发现这个边权<=5,可以考虑拆时间,把每个点拆成5个点,表示不同的时间

转移是把求和和乘转换成max和+

然后对于原图中的一条(u,v,w)其实就是对应了w-1层图中u->最新图中v

然后平移时间的时候用u+n,n+v,0

再发现这个k可以拆成k段做,但是这个东西不能做...所以我们会发现我们只需要一个[1,n]的矩阵乘来过渡中间的部分

需要预处理每个2^的转移矩阵...

所以复杂度是$O(n^2*k*log + n^3log)$

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN = 600;
int n, m, T, k, c[MAXN],tot;
int id[MAXN][MAXN],a[MAXN][MAXN];
ll A[MAXN];

struct festival {
	int t, x, y;
	festival(int t=0,int x=0,int y=0):t(t),x(x),y(y) {};
	bool operator<(const festival &x)const {
		return t < x.t;
	}
} t[MAXN];

struct Mat {
	ll s[MAXN][MAXN];
	Mat() {
		memset(s,-0x3f3f3f3f,sizeof(s));
	}
	Mat operator*(const Mat &x)const {
		Mat 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.s[i][j] = max(c.s[i][j], s[i][k] + x.s[k][j]);
				}
			}
		}
		return c;
	}
} Q[35];

void Mul(Mat Q) {
	static ll B[MAXN];
	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.s[k][j]);
		}
	}
	for(int i = 1; i <= tot; ++i)A[i] = B[i];
}

inline void output(Mat Q) {
	for(int i=1; i<=tot; ++i) {
		for(int j=1; j<=tot; ++j) {
			printf("%lld ",Q.s[i][j]);
		}
		puts("");
	}
	return ;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &T, &k);
	tot = n;
	for(int i = 1; i <= n; ++i)
		scanf("%d", &c[i]);
	for(int i = 1; i <= n; ++i)
		id[i][0] = i;
//	printf("%lld?\n",Q[0].s[1][1]);
	for(int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		for(int j = 1; j < w; ++j)
			if(!id[u][j])
				id[u][j] = ++tot;
		for(int j = 1; j < w; ++j)
			Q[0].s[id[u][j - 1]][id[u][j]] = 0;
		Q[0].s[id[u][w - 1]][v] = c[v];
	}

	for(int i = 1, x, y, z; i <= k; ++i) {
		scanf("%d%d%d", &x, &y, &z);
		t[i] = (festival) {
			x, y, z
		};
	}
	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];
//		output(Q[i]);
	}
	//鍊嶅
	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;
//		printf("%d?%d\n",i,dt);
		for(int j = 30; j >= 0; --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;
}