time limit per test2.5 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a connected undirected weighted graph consisting of n vertices and m edges.
You need to print the k-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).
More formally, if d is the matrix of shortest paths, where di,j is the length of the shortest path between vertices i and j (1≤i<j≤n), then you need to print the k-th element in the sorted array consisting of all di,j, where 1≤i<j≤n.
Input The first line of the input contains three integers n,m and k (2≤n≤2⋅105, n−1≤m≤min(n(n−1)2,2⋅105), 1≤k≤min(n(n−1)2,400) — the number of vertices in the graph, the number of edges in the graph and the value of k, correspondingly.
Then m lines follow, each containing three integers x, y and w (1≤x,y≤n, 1≤w≤109, x≠y) denoting an edge between vertices x and y of weight w.
It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices x and y, there is at most one edge between this pair of vertices in the graph).
Output Print one integer — the length of the k-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).
Examples inputCopy 6 10 5 2 5 1 5 3 9 6 2 2 1 3 1 5 1 8 6 5 10 1 6 5 6 4 6 3 6 2 3 4 5 outputCopy 3 inputCopy 7 15 18 2 6 3 5 7 4 6 5 4 3 6 9 6 7 7 1 6 4 7 1 6 7 2 1 4 3 2 3 2 8 5 3 6 2 5 5 3 7 9 4 1 8 2 1 1 outputCopy 9
题目大意：求所有两点间的第K大路径。
直接暴力必然会TLE，但是由于K比较小，所以我们必然只需要把前K大的边存下来跑最短路，然后就AC了。
对于每个点跑最短路。
因为边很少，每次更新的点也少，所以我们需要把这些点记录一下，来清空，不能每次O（n）去清空，很显然（但是我sb了，直接TLE）。
AC代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,m,k,d[N],flag,vis[N],st[N]; int head[N],nex[N<<1],to[N<<1],w[N<<1],tot; vector<int> res; struct node{ int u,v,w; }t[N]; inline bool cmp(node a,node b){return a.w<b.w;} inline void add(int a,int b,int c){ to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot; } void dijkstra(int x){ priority_queue<pair<int,int> > q; d[x]=0; q.push({0,x}); vector<int> tem; while(q.size()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=nex[i]){ if(d[to[i]]>d[u]+w[i]){ d[to[i]]=d[u]+w[i]; st[to[i]]++; if(st[to[i]]==1) tem.push_back(to[i]); if(!vis[to[i]]) q.push({-d[to[i]],to[i]}); } } } for(int i=0;i<tem.size();i++) res.push_back(d[tem[i]]); d[x]=0x3f3f3f3f3f3f3f3f; vis[x]=0; st[x]=0; for(int i=0;i<tem.size();i++) d[tem[i]]=0x3f3f3f3f3f3f3f3f,vis[tem[i]]=0,st[tem[i]]=0; } signed main(){ cin>>n>>m>>k; memset(d,0x3f,sizeof d); for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&t[i].u,&t[i].v,&t[i].w); sort(t+1,t+1+m,cmp); for(int i=1;i<=k&&i<=m;i++) add(t[i].u,t[i].v,t[i].w),add(t[i].v,t[i].u,t[i].w); for(int i=1;i<=n;i++) dijkstra(i); sort(res.begin(),res.end()); cout<<res[k*2-1]<<endl; return 0; }