暂无

无

摸了_(:з」∠)_

出行 摸一周

无

记忆化搜索（做题太慢了）

也摸了_(:з」∠)_

无

来源：洛谷 p3959 逛公园

tag:记忆化搜索/剪枝/最短路

概述：一张有向图，无自环和重边、负边，存在0边，求从起点到终点长度不超过最短路+K的方案数；可能存在无穷种方案，判断这种情况。

答案：进行dfs搜索从每个点距离起点长度为其最短路+i$(0\le i\le K)$到终点总距离符合要求的方案数，用数组记录之，并加以剪枝；无穷种方案即存在某个点位于一条合法的途径中，这个点连出一条0环，判断的方法就是在dfs中加入拓扑排序的成分。

comments：灵活运用基于最短路的剪枝。