C++(clang++11) 解法, 执行用时: 443ms, 内存消耗: 2808K, 提交时间: 2021-04-03 19:49:41

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

const int N=25;
struct mat{
	int r,c;
	ll a[225][225];
	mat(){
		r=c=0;
		memset(a,0x3f,sizeof(a));
	}
	mat operator * (const mat& T)const{
		mat res;
		res.r=r; res.c=T.c;
		for(int i=0;i<res.r;++i)
			for(int k=0;k<c;++k)
				for(int j=0;j<res.c;++j)
					res.a[i][j]=min(res.a[i][j],a[i][k]+T.a[k][j]);
		return res;
	}
};
mat fpw(mat x,ll k){
	assert(k);
	mat res=x;--k;
	while(k){
		if(k&1)res=res*x;
		x=x*x;k>>=1;
	}
	return res;
}
int n,m,A,B,g[N][N];
int getid(int x,int y){return x*(B+1)+y;}
ll k;
int main() {
	std::ios::sync_with_stdio (0);
	cin>>n>>m>>k>>A>>B;
	mat trans;
	trans.r=trans.c=n*(B+1);
	for(int i=0;i<m;++i){
		int x,y,c;
		cin>>x>>y>>c;
		--x,--y;
		for(int j=0;j<=B;++j) 
			trans.a[getid(x,j)][getid(y,j)]=min(trans.a[getid(x,j)][getid(y,j)],(ll)c);
	}
	for(int i=0;i<A;++i){
		int x,y;
		cin>>x>>y;
		--x,--y;
		for(int j=0;j<B;++j){
			int va;
			cin>>va;
			trans.a[getid(x,j)][getid(y,j+1)]=min(trans.a[getid(x,j)][getid(y,j+1)],(ll)va);
		}
	}
	mat st;
	st.r=1; st.c=n*(B+1);
	st.a[0][getid(0,0)]=0;
	mat res=st*fpw(trans,k+B);
	ll ans=0x3f3f3f3f3f3f3f3fll;
	for(int j=0;j<n;++j) ans=min(ans,res.a[0][getid(j,B)]);
	if(ans>1e18) cout<<-1<<'\n';
	else cout<<ans<<'\n';
	return 0;
}