K-th Path CodeForces - 1196F

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <map>
 7 #include <cmath>
 8 #include <iomanip>
 9 using namespace std;
10 
11 typedef long long LL;
12 #define inf (1LL << 60)
13 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
14 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
15 #define per(i,j,k) for(int i = (j); i >= (k); i--)
16 #define per__(i,j,k) for(int i = (j); i > (k); i--)
17 
18 const int N = (int)2e5 + 10;
19 LL tmp[N];
20 LL dis[810][810];
21 int n,m,k;
22 map<int, int> s;
23 int tot;
24 
25 struct node{
26     int u;
27     int v;
28     int w;
29 
30     bool friend operator < (node a,node b){
31         return a.w < b.w;
32     }
33 
34 }o[N];    
35 
36 int ID(int x){
37     if(s.count(x)) return s[x];
38     return s[x] = ++tot;
39 }
40 
41 int main(){
42 
43     ios::sync_with_stdio(false);
44     cin.tie(0);
45 
46     cin >> n >> m >> k;
47 
48     int u,v,w,l = 0;
49     //存边
50     rep(i,1,m){
51         cin >> u >> v >> w;
52         o[l].u = u;
53         o[l].v = v;
54         o[l++].w = w;
55     }
56     //sort边，取前K条
57     sort(o,o + m);
58     
59     rep(i,1,805) rep(j,1,805){
60         if(i == j) dis[i][j] = 0;
61         else dis[i][j] = inf;
62     }
63 
64     //建图
65     rep__(i,0,min(m,k)){
66         dis[ID(o[i].u)][ID(o[i].v)] = dis[ID(o[i].v)][ID(o[i].u)] = o[i].w;
67     }
68 
69     rep(k,1,tot) rep(i,1,tot) rep(j,1,tot){
70         dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
71     }
72     
73     l = 0;
74     rep(i,1,tot) rep(j,i + 1,tot){
75         tmp[l++] = dis[i][j];
76     }
77 
78     sort(tmp, tmp + l);
79 
80     cout << tmp[k - 1] << endl;
81 
82     getchar();getchar();
83 
84     return 0;
85 }