rt

我的矩阵表示从0时刻可以转移到下个时刻的矩阵。所以从0开始乘

#include<bits/stdc++.h>
#define INF 2147483647
#define MAXN 1000000
using namespace std;
int n,m,s,t,k;
struct node
{
	   int u,v,w;
}lu[MAXN];
vector<int> tim[MAXN];
struct matix
{
	   int jz[55][55];
	   void Init()
	   {
	   	    memset(jz,0,sizeof(jz));
	   }
}st[13],mid;
matix mul(matix a,matix b)
{
	  matix c;
	  c.Init();
	  for(int i=1;i<=n;i++)
	  {
	  	  for(int k=1;k<=n;k++)
	  	  {
	  	  	  for(int j=1;j<=n;j++)
	  	  	  {
	  	  	      c.jz[i][j]+=a.jz[i][k]*b.jz[k][j];	  
	  	  	  }
	  	  }
	  }
	  return c;
}
matix my_pow(matix a,int b)
{
	  matix base;
	  base.Init();
	  for(int i=1;i<=n;i++) base.jz[i][i]=1;
      while(b)
      {
      	  if(b&1) 
      	  {
      	  	 base=mul(base,a);
      	  }
      	  a=mul(a,a);
      	  b>>=1;
      }
      return base;
}
int cnt;
bool check(int now)
{
	 
	 for(int i=0;i<=11;i++)
	 {
	 	 st[i].Init();
	 	 for(int j=1;j<=cnt;j++)
		 {
             if(lu[j].w<=now)
             {
             	st[i].jz[lu[j].u][lu[j].v]=1;
             	st[i].jz[lu[j].v][lu[j].u]=1;
             }
	     }
	 }
	 for(int i=0;i<=11;i++)
	 {
	 	for(int j=0;j<tim[(i+1)%12].size();j++)
		 {
		 	 int now1=tim[(i+1)%12][j];
		 	 for(int t=1;t<=n;t++)
		 	 {
		 	 	 st[i].jz[t][now1]=0;
		 	 }
		 }
	 }
	 mid.Init();
	 for(int i=1;i<=n;i++)
	 {
	 	 mid.jz[i][i]=1;
	 }
	 for(int i=0;i<=11;i++)
	 {
	 	 mid=mul(mid,st[i]);
	 }
//	 for(int i=1;i<=n;i++)
//	 {
//	 	for(int j=1;j<=n;j++)
//	 	{
//	 		cout<<mid.jz[i][j]<<" ";
//	 	}
//	 	cout<<endl;
//	 }
     int ci=k/12;
     int yu=k%12;
     mid=my_pow(mid,ci);
     for(int i=0;i<yu;i++)
     {
     	 mid=mul(mid,st[i]);
     }
     return mid.jz[s][t]!=0;
}
int maxn;
int vis[100][100];
signed main()
{
	cin>>n>>m>>s>>t>>k;
	for(int i=1;i<=m;i++)
	{
        int u,v,w;
        cin>>u>>v>>w;
		if(vis[u][v]) 
		{
			lu[vis[u][v]].w=w;
		}
		else
		{
			++cnt;
			lu[cnt].u=u;
			lu[cnt].v=v;
			vis[u][v]=vis[v][u]=cnt;
			lu[cnt].w=w;
		}
		maxn=max(maxn,lu[i].w);
	}
	int a;
	cin>>a;
    for(int i=1;i<=a;i++)
    {
    	int t;
    	cin>>t;
		for(int j=0;j<t;j++)
        {
        	cin>>a;
        	for(int v=j;v<=11;v+=t)
        	{
        		tim[v].push_back(a);
        	}
        }
    }
    int l=0,r=10000000,mid,ans=-INF;
    while(l<=r)
    {
    	int mid=(l+r)>>1;
    	if(check(mid))
    	{
    		r=mid-1;
    		ans=mid;
    	}
    	else l=mid+1;
    }
    if(ans==-INF)
    {
    	cout<<"'IMP0SSBLE!!'";
    	return 0;
    }
    cout<<ans<<endl;
}