非常好的一个题，有两种做法
方法1：flody+dp
首先我们确定一个最优行走方案：从 \(1\) 号节点赚到足够钱后通过最短路到达 \(x_1\) ，在 \(x_1\) 赚够足够钱后到达 \(x_2\) ，在 \(x_2\) 赚够足够钱后到达 \(x_3\) ，如此往复后到达终点
现在我们有一个问题：从 \(u\) 到 \(v\) 的路径，到达 \(v\) 点后有许多结局。我们考虑一个非常朴素的 \(dp\) ：\(dp_{i,j}\) 表示走到 \(i\) 号点，剩余钱为 \(j\) 的最少表演次数，但这很明显会 \(TLE\) ，寄
但我们发现我们还有一个东西没用：每个点的权值。我们考虑通过转移顺序优化 \(dp\) ，我们用二元组 \(dp_i = (f,g)\) 表示走到 \(i\) 号点，表演 \(f\) 次且最少表演次数为 \(j\) 。这么做 \(dp\) 很明显是不对的，因为我们不知道 \(f\) 和 \(g\) 优先从哪个转移。但我们如果把 \(w_i\) 从小到大排个序，按照顺序考虑，那这个 \(dp\) 就对了
因为我们考虑假如当前 \(v\) 点的 \(dp\) 值的前驱是从 \(u_1\) 转移过来的，我们现在在考虑 \(u_2\) 对 \(v\) 的贡献，因为我们按照点权大小排了序，则我们可以保证 \(w_{u_1} \leq w_{u_2}\) ，这有什么好处呢？这说明如果出现了 \(f_2 > f_1\) ，则无论 \(g\) 的大小关系如何，我们都会选择用 \(u_2\) 更新。因为 \(g_1 < w_{u_1}\) ，我们让这个人在 \(u_2\) 点赚钱 \(f_2 - f_1\) 次，赚得的钱数 \((f_2-f_1)w_{u_2} \geq w_{u-1} > g_1\) ，因此我们从 \(u_2\) 转移更优。
但是还没完，如果 \(f_1 = f_2\) ，则我们优先考虑 \(g\) 更大的即可
因此我们只需要对图 \(O(n^3)\) 的跑一边 \(flody\) 即可解决问题
最终复杂度 \(O(n^3 + n^2 + n \log {n})\) ，复杂度瓶颈在于 \(flody\)
方法2：dijkstra + dp
我们考虑朴素 \(dp\) ，设 \(dp_{i,j,k}\) 表示走到 \(i\) 点的路径上经过的最小点权的点为 \(w_j\) ，还剩 \(k\) 元的最少赚钱次数。这个 \(dp\) 显然会 \(TLE\) ，因此我们考虑优化他。同上一个做法，我们设 \(dp_{i,j} = (f,g)\) 。然后同样的，我们把 \(f\) 当作第一关键字， \(g\) 当作第二关键字即可。注意，这里并不需要排序，因为我们在 \(dp\) 的状态里记录了上一个转移的点，对于 \(j\) 相同的 \(dp\) 状态， \(w_j\) 的值显然是相同的。
因此我们直接用 \(dijkstra\) 优化 \(dp\) 转移即可
最终复杂度 \(O((n^2 + nm) \log n)\)
标签：CF1801D,复杂度,flody,转移,way,home,考虑,我们,dp From： https://www.cnblogs.com/fox-konata/p/17727278.html