其实是参考洛谷上某篇题解的思路；
先求出两个dis数组表示从1走和从n走的最短路；
转移方程：dp[v][dis1[u]-dis1[v]+w+j]+=dp[u][j];
转移顺序要注意一下呢，肯定是先枚举第二维；
dis1[u]-dis1[v]+w+j>=j;
因为有等号，即有同层之间的转移，第一维也不能随便枚举；
如果没有0边，我们可以考虑按dis1从小到大枚举，和dijkstra很像，可以保证更新顺序是对的；
有了零边就要考虑连续好几个零边之间的转移，这个可以把0边挑出来拓扑排序；
关于-1的判断，把零边挑出来之后是可以知道那些点是在零环中的，再看一下经过这个点的路径有没有满足条件的就好了。
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int maxn=100010; const ll inf=1e12; ll dp[maxn][55],dis[maxn][2]; struct edg{ int nex,to; ll w; }e[maxn*2][2]; struct node{ int id; ll dis; bool operator<(const node&a)const{ return dis>a.dis; } }A,B; int s,flag,head,tail,t1,t2,vis[maxn],last[maxn][2],T,n,m,k,p,x,y,qq[maxn]; int h[maxn],pre[maxn*2],other[maxn*2],t3,du[maxn],tot,in[maxn]; ll z; priority_queue<node>q; void add3(int x,int y){++t3;pre[t3]=h[x];h[x]=t3;other[t3]=y;} void add1(int x,int y,ll z){++t1;e[t1][0].nex=last[x][0];last[x][0]=t1;e[t1][0].to=y;e[t1][0].w=z;} void add2(int x,int y,ll z){++t2;e[t2][1].nex=last[x][1];last[x][1]=t2;e[t2][1].to=y;e[t2][1].w=z;} void dijkstra(int lei){ //lei=0,1为起点,lei=1,n为起点； while(!q.empty())q.pop(); memset(vis,0,sizeof(vis)); for(int i=0;i<=n;++i)dis[i][lei]=inf; if(!lei)s=1;else s=n; dis[s][lei]=0; A.id=s;A.dis=0;q.push(A); while(!q.empty()){ B=q.top();q.pop(); if(vis[B.id])continue; vis[B.id]=1; for(int i=last[B.id][lei];i;i=e[i][lei].nex){ int v=e[i][lei].to; if(vis[v])continue; if(dis[v][lei]>dis[B.id][lei]+e[i][lei].w){ dis[v][lei]=dis[B.id][lei]+e[i][lei].w; A.id=v;A.dis=dis[v][lei]; q.push(A); } } } } struct hehe{ ll dis; int id,u; bool operator<(const hehe&a)const{ if(dis==a.dis)return id<a.id; return dis<a.dis; } }lj[maxn]; void tp(){ for(int i=0;i<=n;++i){ lj[i].dis=inf; lj[i].id=0; } flag=1; head=tail=0; for(int i=1;i<=n;++i)if(in[i]&&!du[i]){ qq[++tail]=i;lj[i].id=tail; } while(head<tail){ int u=qq[++head]; for(int i=h[u];i;i=pre[i]){ int v=other[i]; du[v]--; if(!du[v]){qq[++tail]=v;lj[v].id=tail;} } } for(int i=1;i<=n;++i){ if(in[i]&&du[i]){ if(dis[i][1]+dis[i][0]<=dis[n][0]+k){ flag=0; } } } } int main(){ cin>>T; while(T--){ scanf("%d%d%d%d",&n,&m,&k,&p); t1=t2=t3=0; memset(last,0,sizeof(last)); memset(du,0,sizeof(du)); memset(in,0,sizeof(in)); memset(dp,0,sizeof(dp)); memset(h,0,sizeof(h)); for(int i=1;i<=m;++i){ scanf("%d%d%lld",&x,&y,&z); add1(x,y,z);add2(y,x,z); if(!z){add3(x,y);du[y]++;in[x]=in[y]=1;} } dijkstra(0); dijkstra(1); tp(); if(!flag){puts("-1");continue;} else{ for(int i=1;i<=n;++i){ lj[i].dis=dis[i][0]; lj[i].u=i; } sort(lj+1,lj+n+1); dp[1][0]=1; for(int j=0;j<=k;++j) for(int i=1;i<=n;++i) { int u=lj[i].u; for(int l=last[u][0];l;l=e[l][0].nex){ int v=e[l][0].to; if(dis[u][0]-dis[v][0]+e[l][0].w+j<=k){ dp[v][dis[u][0]-dis[v][0]+e[l][0].w+j]+=dp[u][j]; if(dp[v][dis[u][0]-dis[v][0]+e[l][0].w+j]>=p)dp[v][dis[u][0]-dis[v][0]+e[l][0].w+j]-=p; } } } ll ans=0; for(int i=0;i<=k;++i){ ans+=dp[n][i]; if(ans>=p)ans-=p; } printf("%lld ",ans); } } //system("pause"); return 0; }