题目来源：洛谷P3953
思路
先用SPFA求一遍最短路
在求最短路的同时可以把所有点到终点的最短路求出来 dis数组
注意要反向SPFA 因为从起点开始可能会走到一些奇怪的路上导致时间负责度增加
我们定一个f[u][k]数组为从当前节点u还剩时间k到达终点的方案
原来从u走到终点的最短路径消耗时间为dis[u]
而我们现在考虑走(u,v,w)这条边（不是最短路）
那么比走最短路需要多dis[v]+w-dis[u]的时间
所以f[u][k]=∑f[v][k-(dis[v]+w-dis[u])] （从u到终点上有另一个点v）
记忆化搜索即可
PS：容易错的地方是没有初始化
代码
#include<iostream> #include<cstring> #include<queue> using namespace std; #define maxn 100010 #define INF 1e9+7 int T,n,m,k,p,cnt,limit,ans; int dis[maxn],h1[maxn],h2[maxn],f[maxn][55]; bool vis[maxn],v[maxn][55]; struct Edge { int to; int next; int w; }e1[maxn*2],e2[maxn*2]; void add(int u,int v,int w) { e1[++cnt].to=v; e1[cnt].w=w; e1[cnt].next=h1[u]; h1[u]=cnt; e2[cnt].to=u; e2[cnt].w=w; e2[cnt].next=h2[v]; h2[v]=cnt; } void spfa()//反向SPFA { queue<int> q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=INF; q.push(n); dis[n]=0; vis[n]=1; while(!q.empty()) { int temp=q.front(); q.pop(); vis[temp]=0; for(int i=h2[temp];i;i=e2[i].next) { int v=e2[i].to; if(dis[v]>dis[temp]+e2[i].w) { dis[v]=dis[temp]+e2[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int dfs(int u,int k) { if(v[u][k]) return -1;//如果一条路上一个点第二次到达 说明有环 if(f[u][k]) return f[u][k];//记忆化 v[u][k]=1; if(u==n) f[u][k]=1;//边界条件 到达终点还剩k步方案数为1 else f[u][k]=0;//否则为0 for(int i=h1[u];i;i=e1[i].next) { int v=e1[i].to; int temp=dis[v]-dis[u]+e1[i].w;//判断每一条路相比最短路是否超过k if(temp<=k)//没超过 { int w=dfs(v,k-temp);//继续dfs 记得减去剩余时间 if(w==-1) return f[u][k]=-1; f[u][k]=(f[u][k]+w)%p;//记录方案数 } } v[u][k]=0;//重置点 return f[u][k]; } int main() { cin>>T; while(T--) { cnt=0,ans=0; memset(h1,0,sizeof(h1));//记得初始化 memset(h2,0,sizeof(h2)); memset(f,0,sizeof(f)); memset(v,0,sizeof(v)); cin>>n>>m>>k>>p; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); } spfa(); cout<<dfs(1,k)<<endl;//ans在dfs(1,k)中 } }