LG 3953 逛公园

zcmimi at 
LG 3953 逛公园题意: 求$dis(1,n)<=MinDis(1,n)+K$的路径数用拓扑啊什么的一想就很麻烦。有一种玄学的做法:记忆化搜索$f[x][k]$表示$dis(x,n)<=MinDis(x,n)+k$的路径数。先跑一般反向的最短路,然后 dfs 考虑边$(x,y,w)$,$\because Mindis[x]-Mindis[y]+w<k$$\therefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)]$$\therefore f[x][k] = \sum f[y][k-(Mindis[x]-Mindis[y]+w)]$……