原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个最小值
1.2 题目背景、允许、禁止与限制
背景:
有 nnn 个点和 mmm 条边,每个点有个过路费,每条边有边权
允许:
从起点走到终点,求最小代价
代价为:起点走到终点的边权+经过所有点的过路费最大值
1.3 题目数据范围与猜测
1≤n≤250→O(n3)1 \le n \le 250\to O(n^3)1≤n≤250→O(n3)
1.4 一句话概括题意
有 nnn 个节点,mmm条边,求最短路(定义为起点走到终点的边权+经过所有点的过路费最大值)
2 模型匹配
关键词: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}) 三个点中取最大,凭什么保证这三个点中必出一个最大的过路费
因为 Floyd 的 kkk 是按点权从小到大枚举的。当 kkk 正好是真实路径上点权最大的那个点时,这一轮会把路径松弛到最优,此时 max(c[i], c[k], c[j]) 恰好等于真实的最大点权。而之前那些偏大的值,因为路径还没被松弛,不会成为最终答案。
第二个:为什么有可能在 dis 松弛的时候并没有通过中转点 k,还是可以包含上 c [k].v 去计算?
因为Floyd 的 k 只是 “允许使用的中转集合扩容标记”,不代表路径必须经过c[k],因此不会破坏答案正确性,只是多做了一点无效计算。
3 最终代码(禁止抄袭,仅用于参考)