和最短路有关的dp
dp[i][j]表示到i点走的路程比i点最短路多j的方案数
因为要从小往大更新，所以要用最短路对点排序
对于含0边的点要注意还要根据拓扑序更新
某0环上的点u,若dis1[u](距1最短路)+disn[u](距n最短路)<=dis1[n]+k,输出-1
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,cnt,mod,t,k,fl,tot; int dgr[100005]; int twd[100005]; int dis1[100005]; int disn[100005]; int head[100005]; bool vis[100005]; bool zer[100005]; int dp[100005][55]; struct Edge{ int fr; int to; int val; int nxt; }edge[200005]; struct Path{ int fr; int to; int val; int nxt; }path[200005]; struct node{ int u; int w; node(int u,int w):u(u),w(w){} }; struct par{ int u; int ord; int w1; int wn; }prk[100005]; bool operator<(node a,node b){ return a.w>b.w; } int cmp(par a,par b){ if(a.w1==b.w1)return a.ord<b.ord; return a.w1<b.w1; } void init(){ cnt=fl=tot=0; memset(vis,false,sizeof(vis)); memset(twd,-1,sizeof(twd)); memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w){ cnt++; edge[cnt].fr=u; edge[cnt].to=v; edge[cnt].val=w; edge[cnt].nxt=head[u]; head[u]=cnt; } void addpath(int u,int v,int w){ tot++; path[tot].fr=u; path[tot].to=v; path[tot].val=w; path[tot].nxt=twd[u]; twd[u]=tot; } void dijk(){ prk[1].w1=0; priority_queue<node>que; que.push(node(1,0)); while(!que.empty()){ node s=que.top(); que.pop(); if(vis[s.u])continue; vis[s.u]=true; for(int i=head[s.u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(prk[s.u].w1+edge[i].val<prk[v].w1){ prk[v].w1=prk[s.u].w1+edge[i].val; que.push(node(v,prk[v].w1)); } } } memset(vis,0,sizeof(vis)); prk[n].wn=0; que.push(node(n,0)); while(!que.empty()){ node s=que.top(); que.pop(); if(vis[s.u])continue; vis[s.u]=true; for(int i=twd[s.u];i!=-1;i=path[i].nxt){ int v=path[i].to; if(prk[s.u].wn+path[i].val<prk[v].wn){ prk[v].wn=prk[s.u].wn+path[i].val; que.push(node(v,prk[v].wn)); } } } } void Topu(){ memset(vis,false,sizeof(vis)); queue<int>tpu; for(int i=1;i<=cnt;i++){ if(edge[i].val==0){ dgr[edge[i].to]++; } } for(int i=1;i<=n;i++){ if(!dgr[i])tpu.push(i); } while(!tpu.empty()){ int s=tpu.front(); tpu.pop();vis[s]=true; for(int i=head[s];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(edge[i].val==0){ prk[v].ord=prk[s].ord+1; dgr[v]--; if(!dgr[v])tpu.push(v); } } } fl=0; for(int i=1;i<=n;i++){ if(dgr[i])dgr[i]=0; if(!vis[i]){ if(dis1[i]+disn[i]>dis1[n]+k)continue; for(int j=head[i];j!=-1;j=edge[j].nxt){ int v=edge[i].to; if(!vis[v]){ fl=1; } } } } } int main(){ scanf("%d",&t); while(t--){ init(); scanf("%d%d%d%d",&n,&m,&k,&mod); for(int i=1;i<=n;i++){ prk[i].u=i; prk[i].ord=0; prk[i].w1=0x3f3f3f3f; prk[i].wn=0x3f3f3f3f; for(int j=0;j<=k;j++){ dp[i][j]=0; } } for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addpath(v,u,w); } dijk(); for(int i=1;i<=n;i++){ dis1[i]=prk[i].w1; disn[i]=prk[i].wn; } Topu(); if(fl){ printf("-1 "); continue; } sort(prk+1,prk+n+1,cmp); dp[1][0]=1; for(int j=0;j<=k;j++){ for(int i=1;i<=n;i++){ for(int f=head[prk[i].u];f!=-1;f=edge[f].nxt){ int v=edge[f].to; if(dis1[prk[i].u]+edge[f].val+j-dis1[v]<=k){ (dp[v][dis1[prk[i].u]+edge[f].val+j-dis1[v]]+=dp[prk[i].u][j])%=mod; } } } } int ans=0; for(int i=0;i<=k;i++){ (ans+=dp[n][i])%=mod; } printf("%d ",ans); } return 0; }