感想
集训了两个星期,感觉自己水平也在不断提高,挺好。昨天补了五道CF题,今天来更新博客。
这题是CodeForces1196,一场div3的最后一题。
中文题意
给一张\(n\)个点\(m\)条边的无向连通图,让求这张图上所有最短路中,第\(k\)短的最短路(交换起点终点算同一条路)。
解题思路
官方题解是这么说的——
1196F - K-th Path
The main observation is that you don't need more than
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
vertices and no more than 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 -th element of this sorted array.Time complexity:
.I know that there are other approaches that can solve this problem with greater
, but to make this problem easily this solution is enough.哈哈