CF1523F Favorite Game

给定 \(n\) 个传送门和 \(m\) 个地点。传送门需要提前前往才能打开，你可以不用任何时间传送到任何一个传送门，你可以步行 \(1\) 个单位 \(1\) 秒。每个任务要求你在第 \(t_i\) 秒在某个地点，求能完成任务的数目最大值。你可以从任意地点开始。

\(0\leq n\leq14\) ， \(1\leq m\leq100\) ， \(1\leq x_i,y_i\leq10^6\) ， \(1\leq t_i\leq 10^9\) 。

首先肯定是状压传送门的状态，于是有一个朴素的暴力 \(f[i][j][k]\) 表示现在打开的门状态为 \(i\) ，在地点 \(j\) ，完成了 \(k\) 个任务的最短用时。这样的话转移需要向打开下一个传送门或前往下一个任务地点转移，复杂度 \(O(2^n\times(n+m)^2\times n)\) ，不可过。

考虑到当人在任务地点时，时间一定是 \(t_i\) ，在传送门时，具体在哪一个点不重要。因此考虑分开计算这 \(2\) 种情况，各可以省下 \(1\) 维状态。

设 \(f[i][j]\) 表示传送门集合为 \(i\) ，完成 \(j\) 个任务，现在在传送门的最短时间

\(g[i][j]\) 表示传送门集合为 \(i\) ，现在在 \(j\) 点的最大完成任务（此时时间为 \(t_j\) ）。

那么还需要预处理出所有传送门集合到某个点的距离。

这样预处理复杂度 \(O(2^n\times n\times(n+m))\) ，转移复杂度也是 \(O(2^n\times n\times(n+m))\) （从 \(4\) 个方面转移：现在在传送门/任务点，接下来去打开传送门/另一个任务点）。可过。