为了大家更方便思考问题
我给出以上数据的图
这些的正确输出应该都是1，而有些题解输出-1
我对这个错误的分析是（我一开始也错了）
1.没过第1、2个数据是没有判断0环在不在可行路径中就直接输出-1
2.直接按所有0边的图拓扑排序会造成非0环上的点被当作0环上的点
什么意思呢？
请看第三幅图
如果仅仅是按0边建，您会发现入度为0的点是没有的，也就是5，6，7，2，3，4全在0环上？显然不是
注意！拓扑排序后剩下的不仅仅是0环，还有0环连出去的路径，所以您需要怎么做？
思考一下。。。
除了对所有0边建图跑拓扑排序，您可以对所有0边反向建，再跑拓扑排序
那么这时正图入度不为0且反图入度不为0的点才真的在0环上
by salix_leaf @ 2019-04-29 09:37:56
那么我的代码是
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int M=200005;
int n,m,k,p;
struct Edge
{
int sum,h[N];
int v[M],w[M],nxt[M];
void adde(int x,int y,int z)
{
sum++;
v[sum]=y;
w[sum]=z;
nxt[sum]=h[x];
h[x]=sum;
}
void clear()
{
sum=0;
memset(h,0,sizeof(h));memset(v,0,sizeof(v));
memset(w,0,sizeof(w));memset(nxt,0,sizeof(nxt));
}
}e,e0,une,une0;
struct node
{
int pos,dis;int r;
node(int x=0,int y=0):pos(x),dis(y){}
friend bool operator <(node a,node b){return a.dis>b.dis;}
} g[N];
bool cmp(node a,node b){return a.dis!=b.dis?(a.dis<b.dis):(a.r<b.r);}
bool v[N];
priority_queue<node> q;
void dijkstra1()
{
for(int i=1;i<=n;i++) g[i].pos=i,g[i].dis=0x7fffffff;
memset(v,0,sizeof(v));
g[1].dis=0;
q.push(node(1,0));
while(!q.empty())
{
int x=q.top().pos;q.pop();
if(v[x]) continue;
v[x]=1;
for(int i=e.h[x];i;i=e.nxt[i])
{
int y=e.v[i];
if(g[y].dis>1ll*g[x].dis+e.w[i])
{
g[y].dis=g[x].dis+e.w[i];
q.push(node(y,g[y].dis));
}
}
}
}
int undis[N];
void dijkstra2()
{
memset(undis,127,sizeof(undis));
memset(v,0,sizeof(v));
undis[n]=0;
q.push(node(n,0));
while(!q.empty())
{
int x=q.top().pos;q.pop();
if(v[x]) continue;
v[x]=1;
for(int i=une.h[x];i;i=une.nxt[i])
{
int y=une.v[i];
if(undis[y]>1ll*undis[x]+une.w[i])
{
undis[y]=undis[x]+une.w[i];
q.push(node(y,undis[y]));
}
}
}
}
bool ine0[N];
int ind[N];
int unind[N];
void topo1()
{
int cnt=0;
queue<int> q;
for(int i=1;i<=n;i++)
if(ine0[i]&&ind[i]==0)
g[i].r=++cnt,q.push(i);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=e0.h[x];i;i=e0.nxt[i])
{
int y=e0.v[i];
ind[y]--;
if(ind[y]==0)
g[y].r=++cnt,q.push(y);
}
}
}
void topo2()
{
int cnt=N;
queue<int> q;
for(int i=1;i<=n;i++)
if(ine0[i]&&unind[i]==0)
g[i].r=--cnt,q.push(i);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=une0.h[x];i;i=une0.nxt[i])
{
int y=une0.v[i];
unind[y]--;
if(unind[y]==0)
g[y].r=--cnt,q.push(y);
}
}
}
int f[55][N];
int pos[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
e.clear();e0.clear();une.clear();une0.clear();
memset(ine0,0,sizeof(ine0));
memset(ind,0,sizeof(ind));
memset(unind,0,sizeof(unind));
scanf("%d%d%d%d",&n,&m,&k,&p);
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
e.adde(a,b,c);
une.adde(b,a,c);
if(c==0)
{
ine0[a]=ine0[b]=1;
ind[b]++;unind[a]++;
e0.adde(a,b,c);une0.adde(b,a,c);
}
}
dijkstra1();
dijkstra2();
topo1();
topo2();
bool ok=0;
for(int i=1;i<=n;i++)
if(ind[i]&&unind[i]&&1ll*g[i].dis+undis[i]<=1ll*g[n].dis+k)//g[i].dis+undis[i]+k<=g[n].dis
{ok=1;break;}
if(ok){printf("-1\n");continue;}
sort(g+1,g+n+1,cmp);
for(int i=1;i<=n;i++) pos[g[i].pos]=i;
memset(f,0,sizeof(f));
f[0][pos[1]]=1;
for(int more=0;more<=k;more++)
{
for(int x=1;x<=n;x++)
{
if(f[more][x]==0) continue;
for(int i=e.h[g[x].pos];i;i=e.nxt[i])
{
int y=e.v[i];
int tmp=g[x].dis+more+e.w[i]-g[pos[y]].dis;
if(tmp<=k)
{
f[tmp][pos[y]]+=f[more][x];
while(f[tmp][pos[y]]>=p) f[tmp][pos[y]]-=p;
}
}
}
}
int ans=0;
for(int i=0;i<=k;i++) ans=(ans+f[i][pos[n]])%p;
printf("%d\n",ans);
}
return 0;
}
```
***如果您发现您的数据可以hack我，请尽快把我叉掉，不要让我误导他人qwq***
~~管理员您看我这么有诚意就加一个hack数据呗~~
by salix_leaf @ 2019-04-29 09:38:50
@[chen_zhe](/space/show?uid=8457)
by Smile_Cindy @ 2019-04-29 09:43:14
@[Alpha](/space/show?uid=87058) 谢谢qwq
by salix_leaf @ 2019-04-29 09:43:56
受教了
by Imakf @ 2019-04-29 09:47:08
经测试
题解中使用了拓扑排序的目前只有
[这个](https://www.luogu.org/blog/user34444/solution-p3953)qwq和[这个](https://www.luogu.org/blog/user26242/noip2017d1t3-xie-ti-bao-gao)可以过这组数据
tql！！！
by salix_leaf @ 2019-04-29 10:03:20
不用拓扑排序也可能被卡
如果判-1的时候，某个零环不能被任何一条合法路径覆盖，则必须忽略这个零环
也就是，如果两个方向的最短距离之和过大，则这个点需要删除
by Hope2075 @ 2019-04-29 10:12:46
@[i_m_a_](/space/show?uid=86649)
嗯我想我写到了这个呢qwq
上面：1.没过第1、2个数据是没有判断0环在不在可行路径中就直接输出-1
by salix_leaf @ 2019-04-29 10:19:36
@[salix_leaf](/space/show?uid=59700)
应该是吧
这是我去年写的
```cpp
bool test(){
for(int i=1;i<=n;i++){
//if((dis[i]+disa[i]<=disa[1]+k)){
if(iszero[i]){
return true;
}
//}else{
// head[i]=0;
//}
}
return false;
}
```
我的做法：如果在可行路径上某个点在零环上，就判无解
注释掉判是否在可行路径上的部分就全WA了
by Hope2075 @ 2019-04-29 10:26:27
@[salix_leaf](/space/show?uid=59700)
“除了对所有0边建图跑拓扑排序，您可以对所有0边反向建，再跑拓扑排序”
也可以卡：
```
1
9 10 0 1000
1 5 1
5 9 1
5 2 0
2 3 0
3 4 0
4 2 0
5 6 0
6 7 0
7 8 0
8 6 0
```
by Hope2075 @ 2019-04-29 10:37:24