几个月前就已经打算写一个定期推荐好题目的文章，但是因为忙于准备 final，所以一直没有开始写。具体的形式大概和 Petr 博客最后的那样，推荐一道我自己觉得有意思的题目，大概以每周一至两道题的速度吧。
如果对于少儿编程感兴趣的话，可以到有渔编程和我进行交流。
在文章中我会给出题目的大致内容和分阶段的解题思路，但是大部分题目应该是没有公开的提交地址和数据的。如果想要实现并提交的话可以多找几个人大家对拍一下。
初期的题目以简单题为主，也希望大家给我一些反馈，我也会根据反馈在题目的难度上进行调整。同时如果碰到没有学习过的算法/数据结构的话也可以告诉我，我会在下一次的内容中加上一些比较好的博客/学习资料。
I、题目描述
给出一张 n 个点 m 条边的有向图 ，每经过第 i 条边一次会被收取 的路费，保证存在1 到 n 的路径。
正值五一，政府决定对所有从 1 到 n 的旅客，减免一定的路费。专家给出了常数 K，路费将按照如下的方式进行减免，对于一条从 1 到 n 的路径 p：
• 如果 p 中包含了小于等于 K 条边，则不作减免，即路费为所有经过的边的 的和。
• 如果p中包含了超过K条边，则只收取费用最高的K条边的路费，其余路费被减为0。下面是一个例子：
考虑路径 1 → 2 → 3 → 8：
• 当 K ≥ 3 的时候，因为这条路几种只有三条边，所以路费始终为 14。
• 当 K = 2 的时候，1 → 2 被减免了，路费为 12。
• 当 K = 1 的时候，1 → 2 和 2 → 3（或者 3 → 8）被减免了，路费为 6。
同时不难发现在这张图中无论 K 等于几，最优的路径都是 1 → 4 → 7 → 5 → 8。现在给出这张图以及常数 K，你需要计算从 1 到 n 最少需要多少路费。
数据范围 ，时间限制 3s。
题解
前置技能
图上的单源最短路算法
暴力
在答案的路径中，一定存在一个临界值，使得大于等于临界值的所有边都需要缴纳路费， 小于临界值的所有边都不需要缴纳路费。
考虑枚举这个临界值 M ，则所有 小于 M 的道路在这种情况下都不需要支付路费，而
大于等于 M 的道路的路费仍然是 。
于是构造新图 ，把 G 中所有小于 M 的边都赋值为 0，其余边保持权值不变。一条路径的临界值可以是 M 当且仅当这条路径在 G 中经过了恰好 K 条没有被赋值为 0 的边。
于是我们需要求 1 到 n 经过了恰好 K 条非 0 边的所有路径中，边权和最小的路径。这可以在拆点后跑最短路，即新建一张 n × (K + 1) 个点的无向图 ，其中对于每一个原图中的点 ui，都新建 K + 1 个点 至 。对于原图中的一条 到 中的边，分情况考虑：
• 如果这条边边权为 0，则所有的 到 连一条边权为 0 的边。
• 如果这条边边权为 ，则所有的 到 连一条边权为 的边。
不难发现 的意义就是到达 i 经过了恰好 k 条非 0 边的最短路。那么 到 的最短路就是答案。
同时也要考虑经过的边不到 K 条的情况，这种情况只需要在 G 中跑一下 1 到 n 的最短路，和之前的答案取较小值（为什么？）。
在这个算法中，我们需要跑 次 个点， 条边的最短路，使用迪杰斯特拉算法可以达到 的时间复杂度。
上述算法其实是有问题的，考虑一条路径分别经过三条长度为 1, 2, 2 的边，在 K = 1 时：
• 如果枚举到临界值为 1，那么这时经过了两条非 0 边 2, 2，这条路径不会被计入答案
• 如果枚举到临界值大于等于 2，那么这时经过了零条非 0 边，这条路径也不会被计入答案。
解决方案很简单，我们可以人为的规定边的大小顺序：
把所有边按照边权从小到大排序， 边权相同的边任意排序。这时我们得到了边的一个顺序。之后我们就不必枚举确切的临界值了， 只需要枚举一条边 i，把排在他前面的边权都赋值为 0，在他之后的边权都保持不变。然后在这张图上用之前的方法求解恰好经过 K 条边的最短路即可（为什么这样就对了？）
通过这种方法，就能把时间复杂度降到 。
三分法求解单峰函数极值。
在这个问题中，令 f (i) 为我们选取的临界边为 i 的时候的最短路，那么最后的答案就是
，即求解函数 的极值。
如果函数 是凸的，那么可以三分求解，这样只需要求 次最短路即可，时间复杂度能降到 。
但是在这题中函数 不一定满足凸性，因此上述的方法就行不通了。（试着构造一下）
枚举一条临界边 i，按照如下方式变化每一条边的边权得到图
1、如果这条边排在 i 之后，那么把它的边权减去 。
2、 如果这条边排在 i 之前，那么把它的边权变成 0。
求出 中 1 到 n 的最短路，设长度为 d。将 作为候选解。
一共有 m + 1 张图 ，这样我们得到了 m + 1 个候选解，取最小值。同时和暴力做法一样，预先求一遍 G 的最短路来处理经过的边数不到 K 条的情况。这样得到的所有解中的最小值就是答案。
在这个做法中，只需要求 m 次 n 个点 m 条边的单源最短路，时间复杂度为 。如何证明这个做法的正确性？
只需要证明如下两点：
1. 对于每一条可能的路径，都存在一张图 使得在这张图中它的权值为实际值。
2. 对于每一条可能的路径，对于所有图 ，在这张图中它的权值大于实际值。
第一条很显然，对于一条经过边数小于等于 K 的路径，他在原图中权值等于实际值；对于一条经过边数大于 K 条的路径，设其第 K + 1 大的路径为 i，则它在 中权值等于实际值。
现在考虑第二条，仍然分情况讨论：
对于一条经过边数小于等于 K 的路径，他在 中，首先总边权被减去了至多 ，之后又被加上了 ，因此权值不会变小。
对于一条经过边数大于 K 的路径，他在原图中，所有边都被计入了总和中，因此权值不会变小。设这条路径中第 K + 1 大的路径为 j，在 中的权值分情况讨论：
• 如果 i 在 j 之后，那么这时路径中只有小于等于 K 条边在 中非 0，这些边在最后加上 后权值不变。但是这时，考虑所有在路径中是前 K 条但是在最短路中权值是 0 的边，他们的权值在最后都被记为 了，因此这些边的贡献不会减小，于是路径的总权值不会变小。
• 如果 i 在 j 之前，那么这时路径中有大于 K 条边在 中为 0，其中前 K 条边在加上 后权值不变，但是余下的边 k 实际的贡献为 0，但是在这时贡献为 ，因此这些边的贡献增加了，于是路径的总权值增加了。
综上所述，我们证明了这个贪心的算法是正确的。