====== 2020/08/01--2020/08/07======
----
===== 团队训练 =====
暂无
----
===== 王瑞琦 =====
===比赛===
无
===专题===
摸了_(:з」∠)_
===== 冯宇扬 =====
出行 摸一周
===== 常程 =====
===比赛===
无
===专题===
[[2020-2021:teams:no_morning_training:shaco:知识点:搜索:记忆化搜索|记忆化搜索]]（做题太慢了）
----

===== 本周推荐 =====
==== 王瑞琦 ====
也摸了_(:з」∠)_
==== 冯宇扬 ====
无
==== 常程 ====
**来源**：洛谷 p3959 逛公园

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

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

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

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