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

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
 
 
 
#ifdef _MSC_VER
#define scanf scanf_s
#endif // _MSC_VER
 
#ifndef ONLINE_JUDGE
#define debug(x) std::cout<<x<<std::endl;
#else
#define debug(x) ;
#endif
 
using namespace std;
 
const long long INF = static_cast<long long>(1e15 + 7);
 
const int MAXN = 2e5 + 5;
const int MAXM = 2e5 + 5;
 
struct EDGE {
	int from, to, weight;
	EDGE(int f, int t, int w):from(f),to(t),weight(w){}
};
 
int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	vector<EDGE> edge;
	for (int i = 0; i < m; ++i) {
		static int f, t, w;
		scanf("%d%d%d", &f, &t, &w);
		edge.push_back(EDGE(f, t, w));
	}
	sort(edge.begin(), edge.end(), [](const EDGE& a, const EDGE& b) {return a.weight < b.weight; });
	int up = min(k, m);
	vector<vector<long long>> dis(2*k, vector<long long>(2*k, INF));
	vector<int> points;
	for (int i = 0; i < up; ++i) {
		points.push_back(edge[i].from);
		points.push_back(edge[i].to);
	}
	sort(points.begin(), points.end());
	auto ed = unique(points.begin(), points.end());
	map<int, int> bij;
	for (auto it = points.begin(); it != ed; ++it) {
		bij[*it] = it - points.begin();
	}
	for (int i = 0; i < up; ++i) {
		dis[bij[edge[i].from]][bij[edge[i].to]] = edge[i].weight;
		dis[bij[edge[i].to]][bij[edge[i].from]] = edge[i].weight;
	}
	for (int s = 0; s < 2 * k; ++s) {
		for (int i = 0; i < 2 * k; ++i) {
			for (int j = 0; j < 2 * k; ++j) {
				if (dis[i][s] + dis[s][j] < dis[i][j]) dis[i][j] = dis[i][s] + dis[s][j];
			}
		}
	}
	vector<long long> tmp;
	for (int i = 0; i < 2 * k; ++i) {
		for(int j=i+1;j<2*k;++j){
			tmp.push_back(dis[i][j]);
		}
	}
	sort(tmp.begin(), tmp.end());
	printf("%lld\n", tmp[k - 1]);
	return 0;
}