题目链接:https://vjudge.net/problem/CodeForces-1196F
题意:从图中找出第K短的最短路,最短路:从一个点到另一个的最短距离。
思路:题目说了,每两个点之间的边小于等于1,那么如果我们只取K条边,
那么顶点数 V∈[K,2K],所以我们一定可以在K条边中的到第K短的最短路。
当然我们先要把所有变来一个sort,取权值小的K条边。
之后跑一个floyd就可以了,然后把所有最短路存下来,找出第K小的最短路。
ps(这里的编号很方便,我是参考另一个大佬的,这里说明一下,当然也可以和我之前一样,
来个计数的慢慢编号)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std; typedef long long LL;
#define inf (1LL << 60)
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = (int)2e5 + ;
LL tmp[N];
LL dis[][];
int n,m,k;
map<int, int> s;
int tot; struct node{
int u;
int v;
int w; bool friend operator < (node a,node b){
return a.w < b.w;
} }o[N]; int ID(int x){
if(s.count(x)) return s[x];
return s[x] = ++tot;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); cin >> n >> m >> k; int u,v,w,l = ;
//存边
rep(i,,m){
cin >> u >> v >> w;
o[l].u = u;
o[l].v = v;
o[l++].w = w;
}
//sort边,取前K条
sort(o,o + m); rep(i,,) rep(j,,){
if(i == j) dis[i][j] = ;
else dis[i][j] = inf;
} //建图
rep__(i,,min(m,k)){
dis[ID(o[i].u)][ID(o[i].v)] = dis[ID(o[i].v)][ID(o[i].u)] = o[i].w;
} rep(k,,tot) rep(i,,tot) rep(j,,tot){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
} l = ;
rep(i,,tot) rep(j,i + ,tot){
tmp[l++] = dis[i][j];
} sort(tmp, tmp + l); cout << tmp[k - ] << endl; getchar();getchar(); return ;
}