题目大意
给一个非负权边构成的图（有零边），找出从1到n路径长度不超过最短路+k的路径有多少条
思路
要判零环，而且零环要在有用的路径上，那么，从1跑一次dij，再从n跑一次，再判断所有的零边是否在符合要求的路径上，在进行topu，再用一个十分巧妙的dp，dp[i][j],表示比从1到i的最短路多了j的方案数有多少种，按照dis的大小排序后更新，dis一样大 的因为之前枚举过零边，所以有topu序，按照这个进行第二关键字的排序
代码：
#include<bits/stdc++.h> using namespace std; int num,p,head[100005],dis[100005],dish[100005],n,m,sht,k; int he[100005],du[100005],duq[100005],dp[100005][55]; bool flag[100005]; struct ll{ int id; int w; }x,y; inline bool operator < (ll xx,ll yy){ return xx.w>yy.w; } priority_queue<ll>q; struct{ int u,v,w; }ed[200005]; struct{ int to,ne,w,from; }a[200005]; struct{ int to,ne,w,from; }e[200005]; struct lulu{ int di,id,top; }d[200005]; int cmp(lulu xx,lulu yy){ if(xx.di==yy.di)return xx.top<yy.top; return xx.di<yy.di; } void cleardi(){ memset(flag,0,sizeof(flag)); memset(dis,0x3f,sizeof(dis)); } void dij(int now){ int i; cleardi(); x.id=now;x.w=0;dis[now]=0; q.push(x); while(!q.empty()){ y=q.top();q.pop(); if(flag[y.id])continue; now=y.id;flag[now]=1; for(i=head[now];i;i=a[i].ne){ if(dis[a[i].to]>dis[now]+a[i].w){ dis[a[i].to]=dis[now]+a[i].w; y.w=dis[a[i].to]; y.id=a[i].to; q.push(y); } } } } void lian(int from,int to,int w){ num++; a[num].to=to; a[num].ne=head[from]; a[num].w=w; head[from]=num; } void lian2(int from,int to,int w){ num++; e[num].to=to; e[num].w=w; e[num].ne=he[from]; he[from]=num; } void clearfind(){ num=0; memset(he,0,sizeof(he)); memset(du,0,sizeof(du)); } void find(){ int i,from,to; clearfind(); for(i=1;i<=m;i++) if(dish[ed[i].u]+ed[i].w+dis[ed[i].v]<=sht+k&&!ed[i].w) //只能将0边放入，因为如果不是将0边放入，则topu后不能很好的判断0环，因为它可能有环，但不是0环 lian2(ed[i].u,ed[i].v,ed[i].w),du[ed[i].v]++; } void cleartopu(){ memset(duq,0,sizeof(duq)); memset(d,0,sizeof(d)); memset(duq,0,sizeof(duq)); } int topu(){ int i,l=1,r=0,now; cleartopu(); for(i=1;i<=n;i++){ if(!du[i]){ duq[++r]=i; d[i].top=r; } } while(l<=r){ now=duq[l];l++; for(i=he[now];i;i=e[i].ne){ du[e[i].to]--; if(!du[e[i].to]){ duq[++r]=e[i].to; d[e[i].to].top=r; } } } for(i=1;i<=m;i++) if(du[ed[i].u]&&du[ed[i].v]&&!ed[i].w)return 1; return 0; } void cleardp(){ memset(dp,0,sizeof(dp)); } void dpp(){ cleardp(); int i,j,kk,now,to,more; for(i=1;i<=n;i++){ d[i].di=dish[i],d[i].id=i; //cout<<d[i].top<<" "; } sort(d+1,d+n+1,cmp); dp[1][0]=1; for(kk=0;kk<=k;kk++) for(j=1;j<=n;j++){ now=d[j].id; if(!dp[now][kk])continue; for(i=head[now];i;i=a[i].ne){ to=a[i].to; more=dish[now]+kk+a[i].w-dish[to]; if(more<=k){ dp[to][more]=(dp[now][kk]+dp[to][more])%p; } } } } void clearlian(){ num=0; memset(head,0,sizeof(head)); } int main(){ int T,i,j,pd,ans=0; scanf("%d",&T); while(T--){ scanf("%d%d%d%d",&n,&m,&k,&p); clearlian(); for(i=1;i<=m;i++){ scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w); lian(ed[i].u,ed[i].v,ed[i].w); } dij(1); for(i=1;i<=n;i++)dish[i]=dis[i]; sht=dis[n];clearlian(); for(i=1;i<=m;i++)lian(ed[i].v,ed[i].u,ed[i].w); dij(n);find();clearlian(); for(i=1;i<=m;i++)lian(ed[i].u,ed[i].v,ed[i].w); pd=topu(); if(pd){ printf("-1 "); continue; } dpp();ans=0; for(i=0;i<=k;i++)ans=(ans+dp[n][i])%p; printf("%d ",ans); } return 0; }