2020.6.26 German Collegiate Programming Contest 2015 prob:10/10/11 rank:1/29

无

本周无

林星涵：https://nanti.jisuanke.com/t/A1408

题意

一共有 $ N $ 个点，其中有 $ P $ 个是要观看的，有 $M$ 条边，有 $G$ 的时间，给出走每条边的时间，和每个点观看所需的时间，还有一个只能使用一次的特殊操作， 从一点到任意另外一点花费 $T$ 的时间，问是否存在一种方案，在 $G$ 内从 $0$ 开始访问每个需要观看的点再返回 $0$。

数据范围

$ N\le 20000 $ $ P \le 15 $ $ M \le 1e5 $ $ G \le 1e5$

题解

由于关联到的点只有最多15个，因此我们只需要求出这15个点到每个点的最短距离，再利状压 $DP$ 处理出回到0点并且访问了每个点的最短时间即可。

陶吟翔：

郭衍培：