CF773D Perishable Roads

lgswdn_SA · 2021-04-08 20:18:48 · 题解

主要是看了官方题解的思路……所以主要也是官方题解的思考步骤……

Observation 1：最终连成的一定是链。假设出现了 a\to u，b\to u 的情况，假设 a\to u 的代价更小，则我们连接 b\to a 后 b 走到 u 的代价一定更小。

Observation 2：既然一定存在代价链上最小的边 x，则我们将每一条边的代价都减去 x，然后所有经过这条边的路径的代价就都是 0。

设 w_i 表示反向链上第 i 条边的代价。对于距离第一条零边 >3 的边，一定有 w_i>w_{i+1}。否则我们将第 i+1 条边换成连向一个零边 k 的出点的边，然后将 i+2,i+3,...,k 全部反向后一定不差，甚至更优。

所以现在唯一出现决策的是 w_{k-2}>w_{k-1} 或者 w_{k-2}\le w_{k-1}。对于 w_{k-2}>w_{k-1}，显然答案为它到 museum 的最短路；对于 w_{k-2}\le w_{k-1}，设边 k-2 的出点为 u，答案为 2w_{k-2}+dis_{u,t}。（t 为 museum）。

考虑建立超级源到每个点 u 的距离为 2\min a_{u,i}。然后走最短路。最后要记得加上减去的 (n-1)x。

http://codeforces.com/contest/773/submission/112301043