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)]