思路
首先没有0边，且k为0的情况就是最短路计数。
如果k不为0，看到k<=50，想到dp。
设f[u][i]表示到达u点比最短路多走i的路径数，转移到v点。
f[u][i]+=f[v][i-(边权-(dis[u]-dis[v]))]
dis[]表示各点到n的最短路距离
如果有0边，需要判断-1的情况，如果在路径中存在0环，就有无数条路线。
具体判断可以用dfs，是否已经到达过并且没有走多余的路。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 const int N=100005; 7 const int M=200005; 8 int T,n,m,k,mod,cnt,cntr,ans,hd[M],hdr[M],dis[N],vis[N],f[N][55],ind[N]; 9 bool inq[N],cir; 10 queue<int>q; 11 struct edge 12 { 13 int to,nxt,val; 14 }v[M],vr[M]; 15 void addedge(int x,int y,int z) 16 { 17 v[++cnt].nxt=hd[x]; 18 v[cnt].to=y; 19 v[cnt].val=z; 20 hd[x]=cnt; 21 }void addedger(int x,int y,int z) 22 { 23 vr[++cntr].nxt=hdr[y]; 24 vr[cntr].to=x; 25 vr[cntr].val=z; 26 hdr[y]=cntr; 27 } 28 int add(int x,int y) 29 { 30 x+=y; 31 if(x>=mod) 32 x-=mod; 33 return x; 34 } 35 void init() 36 { 37 cir=0; 38 cnt=cntr=ans=0; 39 memset(hd,0,sizeof(hd)); 40 memset(hdr,0,sizeof(hdr)); 41 memset(dis,0x3f,sizeof(dis)); 42 memset(vis,0,sizeof(vis)); 43 memset(f,-1,sizeof(f)); 44 } 45 void spfa() 46 { 47 q.push(n); 48 inq[n]=1; 49 dis[n]=0; 50 while(!q.empty()) 51 { 52 int u=q.front(); 53 q.pop(); 54 inq[u]=0; 55 for(int i=hdr[u];i;i=vr[i].nxt) 56 if(dis[vr[i].to]>dis[u]+vr[i].val) 57 { 58 dis[vr[i].to]=dis[u]+vr[i].val; 59 if(!inq[vr[i].to]) 60 { 61 inq[vr[i].to]=1; 62 q.push(vr[i].to); 63 } 64 } 65 } 66 } 67 int dfs(int u,int res) 68 { 69 if(vis[u]&&ind[u]==res) 70 { 71 cir=1; 72 return 0; 73 } 74 if(f[u][res]>=0) 75 return f[u][res]; 76 int t=0; 77 if(u==n&&!res) 78 t++; 79 ind[u]=res; 80 vis[u]++; 81 for(int i=hd[u];i;i=v[i].nxt) 82 { 83 int x=res-(v[i].val-(dis[u]-dis[v[i].to])); 84 if(x>=0&&x<=k) 85 t=add(t,dfs(v[i].to,x)); 86 if(cir) 87 return 0; 88 } 89 vis[u]--; 90 ind[u]=0; 91 f[u][res]=t; 92 return f[u][res]; 93 } 94 int main() 95 { 96 scanf("%d",&T); 97 while(T--) 98 { 99 init(); 100 scanf("%d%d%d%d",&n,&m,&k,&mod); 101 for(int i=1;i<=m;i++) 102 { 103 int x,y,z; 104 scanf("%d%d%d",&x,&y,&z); 105 addedge(x,y,z),addedger(x,y,z); 106 } 107 spfa(); 108 for(int i=0;i<=k;i++) 109 if(!cir) 110 ans=add(ans,dfs(1,i)); 111 if(cir) 112 printf("-1 "); 113 else 114 printf("%d ",ans); 115 } 116 return 0; 117 }