考试的时候灵光一闪，瞬间推出DP方程，但是不知道怎么判-1，然后？然后就炸了。
后来发现，我只要把拓扑和DP分开，中间加一个判断，就AC了，可惜。
看这道题，我们首先来想有哪些情况是-1：只要有零环在满足题目要求的路径上，那么这条路径就可以不停地走，于是就-1了。
如何判有没有零环呢？
机械化地两遍不同方向的SPFA，就知道某个点在不在最短路上，以此建一个最短路图，在最短路图上找零环。于是就拓扑啦。稍加判断就解决了整个题目最关键的-1。
接下来就是DP了，设f[i][j]表示走到i点，走过路程已经超过i点到n点最短路径长度j的方案数。假设我们知道u点的f[u][k]，接下来我们会走到v。那么如果走的这条边正好是最短路上的边，f[v][k]+=f[u][k]；否则，我们根据f[u][k]知道现在已走路程为dis[u]+k，走完这条边后，就是dis[u]+k+w[i]，这些路程会超过v到n的最短路长度dis[u]+k+w[i]-dis[v]这么长，所以，f[v][dis[u]+k+w[i]-dis[v]]+=[u][k]。
大体就是这样，剩下一些小细节就看代码吧。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=+,MAXM=+,MAXK=+,inf=0x3f3f3f3f;
int n,m,Mod,k,e,qe,beg[MAXN],qbeg[MAXN],dis1[MAXN],p[MAXN],dis2[MAXN],nex[MAXM],qnex[MAXM],w[MAXM],qw[MAXM],to[MAXM],qto[MAXM],Indegree[MAXN],f[MAXN][MAXK],cnt,topoorder[MAXN];
inline void read(int &x)
{
int data=,w=;
char ch=;
while(ch!='-'&&(ch<''||ch>''))ch=getchar();
if(ch=='-')w=-,ch=getchar();
while(ch>=''&&ch<='')data=(data<<)+(data<<)+(ch^''),ch=getchar();
x=data*w;
}
inline void chksum(int &a,int b)
{
a+=b;
if(a>Mod)a-=Mod;
}
inline void insert(int x,int y,int z)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
w[e]=z;
qto[++qe]=x;
qnex[qe]=qbeg[y];
qbeg[y]=qe;
qw[qe]=z;
}
inline void init()
{
e=;
memset(beg,,sizeof(beg));
qe=;
memset(qbeg,,sizeof(qbeg));
memset(f,,sizeof(f));
cnt=;
memset(Indegree,,sizeof(Indegree));
}
inline void SPFA()
{
queue<int> q;
for(register int i=;i<=n;++i)dis1[i]=inf,p[i]=;
q.push();
p[]=;
dis1[]=;
while(!q.empty())
{
int x=q.front();
q.pop();
p[x]=;
for(register int i=beg[x];i;i=nex[i])
if(dis1[to[i]]>dis1[x]+w[i])
{
dis1[to[i]]=dis1[x]+w[i];
if(!p[to[i]])
{
p[to[i]]=;
q.push(to[i]);
}
}
}
for(register int i=;i<=n;++i)dis2[i]=inf,p[i]=;
q.push(n);
p[n]=;
dis2[n]=;
while(!q.empty())
{
int x=q.front();
q.pop();
p[x]=;
for(register int i=qbeg[x];i;i=qnex[i])
if(dis2[qto[i]]>dis2[x]+qw[i])
{
dis2[qto[i]]=dis2[x]+qw[i];
if(!p[qto[i]])
{
p[qto[i]]=;
q.push(qto[i]);
}
}
}
}
inline void toposort()
{
queue<int> q;
for(register int x=;x<=n;++x)
for(register int i=beg[x];i;i=nex[i])
if(dis1[to[i]]==dis1[x]+w[i])Indegree[to[i]]++;
for(register int i=;i<=n;++i)
if(!Indegree[i])q.push(i),topoorder[++cnt]=i;
while(!q.empty())
{
int x=q.front();
q.pop();
for(register int i=beg[x];i;i=nex[i])
if(dis1[to[i]]==dis1[x]+w[i])
{
Indegree[to[i]]--;
if(!Indegree[to[i]])q.push(to[i]),topoorder[++cnt]=to[i];
}
}
}
inline void DP()
{
f[][]=;
for(register int j=;j<=k;++j)
{
for(register int p=;p<=cnt;++p)
{
int x=topoorder[p];
for(register int i=beg[x];i;i=nex[i])
if(dis1[to[i]]==dis1[x]+w[i])chksum(f[to[i]][j],f[x][j]);
}
for(register int x=;x<=n;++x)
for(register int i=beg[x];i;i=nex[i])
if(dis1[to[i]]!=dis1[x]+w[i]&&j+dis1[x]+w[i]-dis1[to[i]]<=k)chksum(f[to[i]][j+dis1[x]+w[i]-dis1[to[i]]],f[x][j]);
}
}
int main()
{
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
int T;
read(T);
while(T--)
{
init();
read(n);read(m);read(k);read(Mod);
int mark=;
for(register int i=;i<=m;++i)
{
int u,v,w;
read(u);read(v);read(w);
insert(u,v,w);
}
SPFA();
toposort();
for(register int i=;i<=n;++i)
if(Indegree[i]&&dis1[i]+dis2[i]<=dis1[n]+k)
{
printf("-1\n");
mark=;
break;
}
if(mark)continue;
DP();
int ans=;
for(register int i=;i<=k;++i)chksum(ans,f[n][i]);
printf("%d\n",ans);
}
return ;
}
NOIP2017 逛公园