CodeForces 1196F K-th Path

<iframe frameborder="0" height="900px" scrolling="no" src="https://vjudge.net/problem/description/117618" style="box-sizing: inherit; height: 1868.8px;" width="100%"> </iframe>

感想

集训了两个星期,感觉自己水平也在不断提高,挺好。昨天补了五道CF题,今天来更新博客。

这题是CodeForces1196,一场div3的最后一题。

中文题意

给一张\(n\)个点\(m\)条边的无向连通图,让求这张图上所有最短路中,第\(k\)短的最短路(交换起点终点算同一条路)。

解题思路

官方题解是这么说的——

1196F - K-th Path

The main observation is that you don't need more than min(k,m) smallest by weight edges (among all edges with the maximum weights you can choose any). Maybe there will be a proof later, but now I ask other participant to write it.

So you sort the initial edges and after that you can construct a graph consisting of no more than 2min(k,m) vertices and no more than min(m,k) edges. You just can build the new graph consisting only on these vertices and edges and run Floyd-Warshall algorithm to find the matrix of shortest paths. Then sort all shorted distances and print the k -th element of this sorted array.

Time complexity: O(mlogm+k3) .

I know that there are other approaches that can solve this problem with greater k , but to make this problem easily this solution is enough.

哈哈

上一篇:LeetCode:1489.找到最小生成树里的关键边和伪关键边


下一篇:1617. Count Subtrees With Max Distance Between Cities