这题DP在分层图上按拓扑序进行到底怎么判0环

判断建新图的点和拓扑的点数会多判0环（我建的正图 然后有些同层的图不影响答案但会被判 所以30pts

暴力找环然后判是否在最短路径上也会寄（没交过但过不了自己hack 就是k不为0但是0环在某条次短的路径上

直接看答案是不是0会漏判一个0环（还是正向建图90pts

至于题解第一篇第一种解法 原图有环他怎么根据拓扑序建新图？至少我是没理解 而且这样直接找是判断不了0或1环的吧 只能判断在不在合法路径上

但是感觉思路可以借鉴 先Tarjan看看环是不是0 在判在不在合法路径上 就是有点暴力

实在想不出其他简单的方法了

下面是蒟蒻的代码 没判环90pts

#include<bits/stdc++.h>  
using namespace std; 
const int N = 2e5 + 10 , M = 4e5 + 10 , F = 100 ;
int T;
int n,m,k,p;
int H[N],NE[M],VER[M],EDGE[M],IDX;
struct Node
{
	int u,v,w;
}E[M];
void read(int &a)
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    a=x*f;
}
void write(int x) 
{
    if(x<0) {putchar('-'),x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void link(int u,int v,int w)
{ 
	EDGE[IDX]=w;
	NE[IDX]=H[u];
	VER[IDX]=v;
	H[u]=IDX++;
}
int h[N*F],ne[M*F],ver[M*F],edge[M*F],ind[N*F],idx;
void add(int u,int v,int w)
{
	ind[v]++;
	edge[idx]=w;
	ne[idx]=h[u];
	ver[idx]=v;
	h[u]=idx++;
}
queue<int> q; 
int dis[N],dist[N*F],cnt[N*F];  
bool used[N];
int ans;
void dij() //迪杰
{
	dis[1]=0;
	typedef pair<int,int> PII ;
	priority_queue<PII,vector<PII>,greater<PII> > que; 
	que.push({0,1});
	while(!que.empty())
	{
		int x=que.top().second; que.pop();
		if(used[x]) continue;
		used[x]=1;
		for(int i=H[x];~i;i=NE[i])
		{
			int y=VER[i];
			if(dis[y]>dis[x]+EDGE[i]) dis[y] = dis[x] + EDGE[i] , que.push({dis[y],y}) ;
		}
	}
}
void To_zero() //多测不清空 亲人两行泪
{  
	memset(used,0,sizeof used);
	memset(ind,0,sizeof ind); 
	memset(cnt,0,sizeof cnt); 
	memset(h,-1,sizeof h);
	memset(H,-1,sizeof H);
	memset(dis,0x3f,sizeof dis);
	memset(dist,0x3f,sizeof dist);
	ans = idx = IDX = 0 ; 
} 
signed main()
{   
	scanf("%lld",&T);
	while(T--)
	{ 
		To_zero();  
		read(n);read(m);read(k);read(p);  
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			read(a);read(b);read(c); 
			link(a,b,c);
			E[i]={a,b,c};
		}
		dij();  //预处理1到每个点的最短路 
		for(int i=1;i<=m;i++)
		{
			int u=E[i].u,v=E[i].v,w=E[i].w; 
			int new_k = dis[u] - dis[v] + w ;
			if(new_k==0)  
				for(int j=0;j<=k;j++) // 分层
					add(u+j*n,v+j*n,w);  
			else if(new_k>0&&new_k<=k)  
				for(int j=1;j-1+new_k<=k;j++)    
					add(u+(j-1)*n,v+(j-1+new_k)*n,w);    
		}   // 根据状态转移方程建分层图  
		for(int i=0;i<=k;i++) if(!ind[1+i*n]) q.push(1+i*n),cnt[1+i*n]=i==0?1:0,dist[1+i*n]=i; 
		while(!q.empty())
		{
			int x = q.front(); q.pop();  
			for(int i=h[x];~i;i=ne[i])
			{
				int y=ver[i];  
				if(dist[y]>dist[x]+edge[i]) dist[y]=dist[x]+edge[i],cnt[y] = cnt[x] ;
				else if(dist[y]==dist[x]+edge[i]) cnt[y] += cnt[x], cnt[y]%=p ;
				if(--ind[y]==0) q.push(y);  
			}  
		}    //拓扑决定dp顺序
		for(int x=0;x<=k;x++)
		{   
			ans += cnt[x*n+n]; 
			ans %= p;
		}  //统计答案   
		if(ans) write(ans),putchar('\n');
		else puts("-1"); // 0环会使答案无法统计
	}	 
}        
//u -> v 
//dis[v] = dis[u] + minw 
//dp[v][k] = dis[v] + k  
//dp[v][k] = dis[v] + k = dp[u][x] + w = dis[u] + x + w 
//k = dis[u] - dis[v] + w + x