题目：https://www.luogu.org/problemnew/show/P3953
因为K只有50，所以想到用dp[ cr ][ j ]表示在点cr、比最短路多走了 j 的方案数。（看了TJ才知道）
因为不是DAG，所以没有拓扑序，就用记忆化搜索就好了。
判0环可以用bool数组，而且是栈的样子，表示从自己出发又一模一样地走回来就说明有0环。
0环还要在一条合法路径上才行。判断是dis[cr]+k+dit[cr]<=dis[n]+K。(dit是从n到各点的最短路)还可以用它剪枝。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const int N=1e5+5,M=2e5+5,S=55,INF=0x3f3f3f3f; int T,n,m,K,mod,hd[N],thd[N],xnt,tnt,dis[N],dit[N],f[N][S],ans; bool vis[N],flag,gx[N][S]; struct Ed{ int nxt,to,w; Ed(int n=0,int t=0,int w=0):nxt(n),to(t),w(w) {} }ed[M],ted[M]; int rdn() { int ret=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')(ret*=10)+=ch-'0',ch=getchar(); return ret; } priority_queue<pair<int,int> >q; void dj() { memset(dis,0x3f,sizeof dis);dis[1]=0; memset(vis,0,sizeof vis); q.push(make_pair(-dis[1],1)); while(q.size()) { int k=q.top().second;q.pop(); while(q.size()&&vis[k])k=q.top().second,q.pop(); if(vis[k])break;vis[k]=1; for(int i=hd[k],v;i;i=ed[i].nxt) if(dis[v=ed[i].to]>dis[k]+ed[i].w) dis[v]=dis[k]+ed[i].w,q.push(make_pair(-dis[v],v)); } memset(dit,0x3f,sizeof dit);dit[n]=0; memset(vis,0,sizeof vis); q.push(make_pair(-dit[n],n)); while(q.size()) { int k=q.top().second;q.pop(); while(q.size()&&vis[k])k=q.top().second,q.pop(); if(vis[k])break;vis[k]=1; for(int i=thd[k],v;i;i=ted[i].nxt) if(dit[v=ted[i].to]>dit[k]+ted[i].w) dit[v]=dit[k]+ted[i].w,q.push(make_pair(-dit[v],v)); } } int dfs(int cr,int k) { if(gx[cr][k]){flag=1;return -1;} if(f[cr][k])return f[cr][k]; if(cr==n)f[cr][k]=1;//别return f[cr]=1,万一在终点连了一个0环 gx[cr][k]=1; for(int i=hd[cr],v;i;i=ed[i].nxt) { int w=dis[cr]+k+ed[i].w-dis[v=ed[i].to]; if(w>K||(ll)dis[v]+w+dit[v]>dis[n]+K)continue; (f[cr][k]+=dfs(v,w))%=mod; if(flag)return -1; } gx[cr][k]=0;//! return f[cr][k]; } int main() { T=rdn(); while(T--) { memset(hd,0,sizeof hd);xnt=0; memset(thd,0,sizeof thd);tnt=0; n=rdn();m=rdn();K=rdn();mod=rdn(); int x,y,z; for(int i=1;i<=m;i++) { x=rdn();y=rdn();z=rdn(); ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt; ted[++tnt]=Ed(thd[y],x,z);thd[y]=tnt; } dj(); memset(f,0,sizeof f);memset(gx,0,sizeof gx); flag=0;ans=dfs(1,0); if(flag)ans=-1; printf("%d ",ans); } return 0; }