[20220314联考] 旅行
前言
无码警告!
题目
给一棵 \(n\) 个点 \(m\) 条边的连通图,边权为 \(1\),每个点有 \(d_i,c_i\) 表示可以花费 \(c_i\) 的代价到距离 \(i\) 不超过 \(d_i\) 的点,问 \(1\) 到每个点的最小花费。
\(1\le d_i\le n\le 2\times 10^5;1\le c_i\le 10^9;n-1\le m\le n+50.\)
讲解
膜拜DD。
先考虑 \(m=n-1\) 的情况,考虑 \(\tt Dijkstra\) ,我们按转移点的松弛值 \(dp_i+c_i\) 去松弛其它点可保证第一次松弛就是最后一次松弛,我们要做的就是优化这个过程。
直接建点分树,然后随便用点数据结构就可以找出距离当前转移点不超过 \(d_i\) 的未松弛的点。
这个过程我们可以按 DD 的做法,用三元组 \(\{dp_i+c_i,d_i,i\}\) 存储转移点。
然后我们再考虑 \(m\) 更大的时候咋做,其实还是先建一棵生成树,点分,然后对于非树边,称它们所连的点为特殊点,我们每次加三元组把它们也加上即可。
即对于关键点 \(j\) 加上 \(\{dp_i+c_i,d_i-dis_{i,j},j\}\),而 \(dis_{i,j}\) 显然可以 \(O(n(m-n))\) 预处理。
时间复杂度 \(O(n(m-n)\log_2n)\)。
代码
说了无码你还点开干嘛