Codeforces 1196F K-th Path

题目大意是说给定一个无向图,要求出所有的点对之间的最短路之中第k小的值。思路很简单,就是用Floyd算法跑一遍然后排序就行,但是点的数目给的比较多,用邻接矩阵存储会爆内存。注意到第k小的最短路权值至多为第k短的边权,因此选择前k条边连接的至多2k个点,仅仅考虑它们之间的路径来跑最短路,就OK了。

继续阅读“Codeforces 1196F K-th Path”