题解：
之前知道正解并没有写过。。
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
const int N=3e5;
struct re{
int a,b,c;
}e[N],jl[N];
int n,m,k,p,head[N],l,rd[N],tim[N];
void arr(int x,int y,int z)
{
e[++l].a=head[x];
e[l].b=y;
e[l].c=z;
head[x]=l;
}
queue<int> q;
stack<int> S;
int dfn[N],low[N],col[N],color_cnt,sz[N],cnt,tim2[N];
bool ins[N];
void tarjan(int x,int y)
{
dfn[x]=low[x]=++cnt; S.push(x); ins[x]=;
for (rint u=head[x];u;u=e[u].a)
{
rint v=e[u].b;
if (!dfn[v])
{
tarjan(v,x);
dfn[x]=min(dfn[x],low[v]);
}
if (ins[v]) dfn[x]=min(dfn[x],dfn[v]);
}
if (dfn[x]==low[x])
{
color_cnt++;
while ()
{
int y=S.top(); S.pop(); col[y]=color_cnt; ins[y]=; sz[color_cnt]++;
if (y==x) break;
}
}
}
const int INF=5e8;
int dis[N],dis1[N],dis2[N];
struct cmp{
bool operator () (re x,re y)
{
return x.b>y.b;
}
};
priority_queue<re,vector<re>,cmp> Q;
bool vis[N];
void dij(int x)
{
me(vis);
rep(i,,n) dis[i]=INF;
Q.push((re){x,}); dis[x]=;
while (!Q.empty())
{
int x=Q.top().a; Q.pop();
if (vis[x]) continue; vis[x]=;
for (rint u=head[x];u;u=e[u].a)
{
int v=e[u].b;
if (dis[v]>dis[x]+e[u].c)
{
dis[v]=dis[x]+e[u].c;
Q.push((re){v,dis[v]});
}
}
}
}
int f[N][];
const int N2=1.5e7;
re ve[N2];
IL void js(int &x,int y)
{
x=(x+y)%p;
}
bool cmp3(re y,re x)
{
int jl1=dis1[x.a]+x.b;
int jl2=dis1[y.a]+y.b;
return (jl2<jl1)||(jl1==jl2&&tim[y.a]<tim[x.a]);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int T;
read(T);
rep(ttt,,T)
{
l=; me(head); me(dfn); me(low); me(sz); color_cnt=;
read(n); read(m); read(k); read(p); me(rd);
rep(i,,m)
{
int x,y,z;
read(x); read(y); read(z);
jl[i]=(re){x,y,z};
if (z==) arr(x,y,z),rd[y]++;
}
rep(i,,n) if (!rd[i]) q.push(i);
int cnt=;
while (!q.empty())
{
int x=q.front(); q.pop(); tim[x]=++cnt;
for (rint u=head[x];u;u=e[u].a)
{
rint v=e[u].b;
rd[v]--;
if (!rd[v]) q.push(v);
}
}
rep(i,,n) if (!dfn[i]) tarjan(i,);
me(head); l=;
int s=col[],t=col[n];
rep(i,,m)
if (col[jl[i].a]!=col[jl[i].b]) arr(col[jl[i].a],col[jl[i].b],jl[i].c);
dij(s);
rep(i,,n) dis1[i]=dis[i];
me(head); l=;
rep(i,,m)
if (col[jl[i].a]!=col[jl[i].b]) arr(col[jl[i].b],col[jl[i].a],jl[i].c);
dij(t);
rep(i,,n) dis2[i]=dis[i];
int now=dis1[n];
bool tt=;
rep(i,,color_cnt)
if (dis1[i]+dis2[i]<=now+k&&sz[i]>) tt=;
if (tt)
{
cout<<-<<endl;
continue;
}
me(head); l=;
rep(i,,m)
if (col[jl[i].a]!=col[jl[i].b]) arr(col[jl[i].a],col[jl[i].b],jl[i].c);
int ans=;
me(f);
f[s][]=;
rep(i,,n) tim2[col[i]]=tim[i];
rep(i,,n) tim[i]=tim2[i];
int cnt2=;
rep(i,,color_cnt)
rep(j,,)
if (dis1[i]+dis2[i]+j<=now+k)
{
ve[++cnt2]=(re){i,j};
}
sort(ve+,ve+cnt2+,cmp3);
rep(i,,cnt2)
{
re xx=ve[i];
int x=xx.a,y=xx.b;
if (!f[x][y]) continue;
if (x==t) ans=(ans+f[x][y])%p;
for (rint u=head[x];u;u=e[u].a)
{
rint v=e[u].b;
if (e[u].c+y+dis1[x]+dis2[v]<=now+k)
{
int t1=f[v][e[u].c+y+dis1[x]-dis1[v]],t2=f[x][y];
js(t1,t2);
f[v][e[u].c+y+dis1[x]-dis1[v]]=t1;
}
}
}
cout<<ans<<endl;
}
return ;
}
我觉得这细节真的挺多的。。
而且我都不知道我去年怎么写的60分了。。
网上的方法好像比我的简单。。。
首先在0环上我的处理是
先缩点，然后判缩完后的点能否在路径上
如果能在，输出-1
由于这个缩点还是带来了比较大的干扰。。
调试中的几个错都是这个产生的。。
另外最短路据说是线段树优化跑的最快？？
最后的dp还是比较简单的
f[i][j]表示到i点，比原先最短路长j，然后对终点跑一遍最短路来剪枝
然后发现相同dis可以互相转移
所以根据零边拓扑排序一下
网上的判0环的方法比较简单
直接在做的时候 如果扩展到之前的状态 就说明有0环
这很显然啊。。。。
主要刚开始没仔细想这个过程。。
noip至少得留1:30 才能搞完这题吧。。 2:00就比较稳
诶网上最简单的代码好简单啊。。。
直接对s跑一遍最短路，然后直接dp 省掉所有过程啊 而且还挺快的。。。（看来这个剪枝作用也不是很大）
所以下次还是想清楚再写。。。 看看有没有简单的办法
要是写后面这份代码 1小时足够了啊。。。