给定一个图,求 \(s\) 到 \(t\) 的最短路,其中路径的长度是其长度前 \(k\) 大边的长度和。\(n, k \le 1000, m\le 2000\)。
做法
枚举被算入的最小边权 \(w\),所有小于 \(w\) 的边权都可以视为 \(0\),而我们需要确保大于等于 \(w\) 的边至少走了 \(k\) 条。如何实现这一点呢?通过记录已经走了几条边只能做到 \(nmk\)。在赛场上我想到答案关于 \(k\) 或者关于 \(w\) 有着凸性/单峰性,那么可以通过二分来实现。后来被证明似乎是错的。那么怎么做呢?实际上我们可以直接假设已经走了 \(k\) 条边,如果实际上没有走,我们也把没走的补上。具体地,给所有大于等于 \(w\) 的边权减去为 \(w\),求出最短路后加上 \(kw\)。这样,如果实际上走的少了,可以当作我们凭空走了一些长度为 \(w\) 的边;如果走多了,可以当作实际上排在 \(k\) 名以后的一些边也被算了一些代价。这样对于非最优解,我们只会算劣,而最优解一定能被在恰好枚举到正确 \(w\) 的时候构造出来。于是做完了。
标签:25,le,2023.12,边权,T1,南外,长度 From: https://www.cnblogs.com/kyeecccccc/p/17926046.html