这题和最短路计数有很大关系，再加上k只有50，容易让人想到dp，
先设计状态$f[i][j]$表示到$i$点比最短路多走了$j$长度的方案数，接下来思考转移
考虑一条边$u->v$边权为$w$，从$f[u][j]$能转移到$f[v]$的哪个状态？
既然是走到$v$比$dis[v]$多走多少，就比较显然了，我们已经走了$dis[u]+j$，从这条边走到$v$再花费$w$的边权，总共比$dis[v]$多走$dis[u]+w-dis[v]$，可转移到$f[v][j-(dis[u]+w-dis[v])]$
（虽然显然但是看题解的时候真不知道啥意思...前面的题解全给化简了...看不出来是啥意义...
而这个式子（显然）有一个性质，就是$dis[u]+w-dis[v]>=0$，当取等时表示这条就是最短路
那么这样转移就会有序无后效性，我们从小到大枚举K转移即可
至于-1的情况应该是出现0环，样例中也有提示，我们可以用dfs，$v[x][res]$如果被重复访问（不花费任何代价就回到这个点）即为-1
可以使用记忆化搜索dp，引用某题解：因为不是每个节点都能够到达节点n的，毕竟这是有向图，反向建图的好处就是可以完全回避进入死胡同的情况，同时也是为了spfa算出到节点n的值，这是一种常用的技巧。似乎不建反图也是对的
还有一些实现细节在代码里需要注意
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=100009; const int maxm=200009; inline int read(){ int ret=0,fix=1;char ch; while(!isdigit(ch=getchar()))fix=ch==‘-‘?-1:fix; do ret=(ret<<1)+(ret<<3)+ch-‘0‘; while(isdigit(ch=getchar())); return ret*fix; } int n,m,k,mod; struct node{ int v,nxt,w; }e[maxm<<1],e2[maxm<<1]; int head[maxn],cnt,head2[maxn],cnt2; inline void add(int u,int v,int w){ e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt; } inline void add2(int u,int v,int w){ e2[++cnt2].v=v;e2[cnt2].w=w;e2[cnt2].nxt=head2[u];head2[u]=cnt2; } int d[maxn]; inline void spfa(){ memset(d,0x7f,sizeof(d)); queue<int> q; q.push(1); d[1]=0; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=e[i].nxt){ int y=e[i].v; if(d[y]>d[x]+e[i].w){ d[y]=d[x]+e[i].w; q.push(y); } } } } bool flag,vis[maxn][55]; ll f[maxn][55]; int dfs(int x,int res){ if(res<0 || res>k)return 0; if(vis[x][res]){ vis[x][res]=0; return -1; } if(f[x][res]!=-1)return f[x][res]; vis[x][res]=1; ll ans=0; for(int i=head2[x];i;i=e2[i].nxt){ int y=e2[i].v; int t=dfs(y,res-(d[y]+e2[i].w-d[x]));//反图所以xy互换 if(t!=-1)(ans+=t)%=mod; else{ vis[x][res]=0; return -1; } } vis[x][res]=0; if(x==1 && res==0)(ans+=1)%=mod;//找到 f[x][res]=ans; return ans; } int main(){ // freopen("testdata (1).in","r",stdin); int T=read(); while(T--){ scanf("%d%d%d%d",&n,&m,&k,&mod); cnt=0;cnt2=0; memset(e2,0,sizeof(e2)); memset(head2,0,sizeof(head2)); memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); for(int i=1,u,v,w;i<=m;i++){ u=read(),v=read(),w=read(); add(u,v,w);add2(v,u,w); } spfa(); memset(f,-1,sizeof(f)); memset(vis,0,sizeof(vis)); flag=0; ll ans=0; for(int i=0;i<=k;i++){ int t=dfs(n,i); if(t==-1)flag=1; else (ans+=t)%=mod; } printf("%d\n",flag==1?-1:ans); } }
[题解]luogu_P3593_[NOIP2017]逛公园（最短路相关计数
原文：https://www.cnblogs.com/superminivan/p/11478245.html