原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个最小值
1.2 题目背景、允许、禁止与限制
背景:
有 nnn 个点和 mmm 条边,每个点有个过路费,每条边有边权
允许:
从起点走到终点,求最小代价
代价为:起点走到终点的边权+经过所有点的过路费最大值
限制:
1.3 题目数据范围与猜测
1≤n≤2501 \le n \le 2501≤n≤250
1.4 一句话概括题意
有 nnn 个节点,mmm条边,求最短路(定义为起点走到终点的边权+经过所有点的过路费最大值)
2 题目破题推导
3 模型匹配
> 格式为:"关键词:...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词:1≤n≤2501 \le n \le 2501≤n≤250,全源最短路 ⟶\longrightarrow⟶ floyd\huge{floyd}floyd
最短路好求,那么过路费最大值怎么办呢?
这时候可以用贪心+递推
就是排序点权(因为floyd不受松弛点顺序的影响),然后对于排完序后的点权求最短路,而已经排好序了,所以只需要找到 ci,cj,ckc_i,c_j,c_kci ,cj ,ck 中的最大值
那么有两个问题:
第一个:为什么可以是 max ({c [i].v, c [k].v, c [j].v}) 三个点中取最大,凭什么保证这三个点中必出一个最大的过路费
因为大部分时候这个 max 算出来的数字偏大,只有刚好轮到放开路径最大点那一轮,算出来的数字才等于真实值。
第二个:为什么有可能在 dis 松弛的时候并没有通过中转点 k,还是可以含上 c [k].v 去计算?
因为Floyd 的 k 只是 “允许使用的中转集合扩容标记”,不代表路径必须经过c[k],因此不会破坏答案正确性,只是多做了一点无效计算。
4 最终代码(禁止抄袭,仅用于参考)