题意：
这道题把我看得懵懵的(不敢相信)，其实就是给你n个点和m条边(无向图)，你要找出来任意两点之间的的最短距离，然后再从其中找出来第k个最小值
题解：
正常思维就是floyd多源最短路算法跑一遍，然后把任意两点之间的距离取出来放在数组里面，再排序。之后打印出第k个就可以了
但是n的范围是2e5，然而数组开不了这么大的，所以这里有一点优化的。因为要求第k大的距离，所以我们对所有边排序，取出来前k条边，用这k条边的端点(可以离散化把点的值变小)来重新构造一个图
至于为什么可以这样做，我们可以实践一下，如果这k条边互相不相连，那么第k个大的边(而且这个边还是最短的，正好相当于两点之间的最短路)，正好符合题意(因为我们这k条边是在所有边中最小的k个，其他的边肯定要大于等于它)
如果相连了，那么也可以构造出来新的更短的距离，只有这个新的两点之间的距离小于等于咱们挑出来的边才会使用到，所以这样也符合题意
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<algorithm> 9 #include<queue> 10 #include<unordered_map> 11 #include<list> 12 using namespace std; 13 #define ll long long 14 const int mod=1e9+7; 15 const ll int inf=1e18+7; 16 17 const int maxn=4e5+5; 18 19 typedef struct 20 { 21 int u; 22 int v; 23 ll int w; 24 }St; 25 St sum[maxn]; 26 27 bool cmp(const St &a,const St &b) 28 { 29 return a.w < b.w; 30 } 31 32 int n,m,k; 33 34 ll int e[2005][2005]; 35 36 void init() 37 { 38 for(int i=0;i<=1505;i++) 39 { 40 for(int j=0;j<=1505;j++) 41 { 42 if(i==j) 43 e[i][j]=0; 44 else 45 e[i][j]=inf; 46 } 47 } 48 } 49 50 int main() 51 { 52 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 53 54 init(); 55 56 cin>>n>>m>>k; 57 58 vector<ll int>v; 59 60 for(int i=0;i<m;i++) 61 cin>>sum[i].u>>sum[i].v>>sum[i].w; 62 63 sort(sum,sum+m,cmp); 64 65 for(int i=0;i<min(m,k);i++) 66 { 67 v.push_back(sum[i].u); 68 v.push_back(sum[i].v); 69 } 70 71 //离散化 72 sort(v.begin(),v.end());//排序 73 v.erase(unique(v.begin(),v.end()),v.end());//去重 74 75 int now=v.size(); 76 77 for(int i=0;i<min(m,k);i++) 78 { 79 sum[i].u=lower_bound(v.begin(),v.end(),sum[i].u)-v.begin()+1;//加一防止点从0开始 80 sum[i].v=lower_bound(v.begin(),v.end(),sum[i].v)-v.begin()+1; 81 82 e[sum[i].u][sum[i].v]=sum[i].w; 83 e[sum[i].v][sum[i].u]=sum[i].w; 84 85 } 86 87 for(int k=1;k<=now;k++) 88 { 89 for(int i=1;i<=now;i++) 90 { 91 for(int j=1;j<=now;j++) 92 { 93 if(e[i][k]+e[k][j]<e[i][j]) 94 { 95 e[i][j]=e[i][k]+e[k][j]; 96 } 97 } 98 } 99 } 100 101 vector<ll int>edge; 102 103 for(int i=1;i<=now;i++) 104 { 105 for(int j=i+1;j<=now;j++) 106 { 107 edge.push_back(e[i][j]); 108 } 109 } 110 111 sort(edge.begin(),edge.end());; 112 113 cout<<edge[k-1]<<endl; 114 115 return 0; 116 }