P6961 [NEERC2017]Journey from Petersburg to Moscow

whhsteven · 2022-08-21 16:36:26 · 题解

试着将现存这篇题解的做法讲得更清楚些。

尝试枚举每一条边，钦定其为答案路径上的第 k 长的边，记其边权为 w_0。将权值 w < w_0 的边的权值都看成 0，将权值 w \ge w_0 的边的权值看成 w - w_0，然后跑最短路，取 \mathrm{dis}_n + kw_0 为这次钦定的答案。

考察这个答案和实际答案的关系。

• 若 w_0 正好等于当前某条最短路上的第 k 大边权，则当前答案大于等于实际答案；

• 若 w_0 大于当前某条最短路上的第 k 大边权，则当前答案还是大于等于实际答案。这是因为：在当前最短路上，存在若干条边（可以是 0 条）本应贡献的小于 w_0 的边权被放大成了 w_0；

• 若 w_0 小于当前某条最短路上的第 k 大边权，则当前答案同样大于等于实际答案。这是因为：在当前最短路上，存在若干条边（可以是 0 条）本不应对最短路长度贡献却实际上产生了贡献。

由此可见，每次钦定出来的答案都是大于等于实际答案的。

还可以看到，只要存在一条答案路径边数不小于 k，答案路径上的第 k 长边就是客观存在的，所以我们一定会至少一次枚举到，并且在这时就一定得到了正确答案。

不过还要注意一个事实：有可能所有的答案路径边数都不足 k。可以发现这时按照上面的方式不能得到正确答案。

当所有的答案路径边数都不足 k 时，按题意显然有答案路径上每一条边对最短路答案的贡献都是其原始边权。所以我们不钦定任何边，直接在原图上跑最短路，就得到了这种情况的正确答案。

易见，在不是这种情况时，原图最短路一定不短于实际答案。

实现时，我们只需要把所有钦定答案和直接在原图上跑出来的最短路取最小值，即可一定得到正确答案。

这道题的难点在于想到枚举一条边钦定其边权为路径上第 k 大边权这样的操作，以及这样操作后的处理方式及其正确性。