AT_abc422_f 题解

本文记载了我看到这题时抽象的思路历程。

看到这个题目，首先花了 分钟否决掉了直接跑最短路的想法，因为你不好定义两个结果的序关系。

然后，开始考虑一种经典的优化方式，费用提前计算。注意到每个点的贡献和之后的边数有关，因此考虑 表示点 到第 个点，距离最后一个点距离为 的最小代价。那么转移的代价就是这个点的点权乘上距离。但是，我们发现，这是一张无向图，我们不好找到一个很好的顺序来转移（这对吗）。因此，我们考虑直接建分层图跑最短路。复杂度 。

然后就 T 飞了。然后赛时写完 AB 就来死磕 F 最后每磕出来喜提 题的好成绩。

然后我们仔细看一下这个转移过程。 然后，你就可以发现，第二维只能从 转移到 。建成分层图就是个 DAG。然后你以这个为阶段转移就可以了。

赛后有人告诉我的时候我感觉自己糖丸了。