F. K-th Path

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;
}