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 $d_{i, j}$ is the length of the shortest path between vertices $i$ and $j$ ($1 \le i < j \le n$), then you need to print the $k$-th element in the sorted array consisting of all $d_{i, j}$, where $1 \le i < j \le n$.


-----Input-----

The first line of the input contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \min\Big(\frac{n(n-1)}{2}, 2 \cdot 10^5\Big)$, $1 \le k \le \min\Big(\frac{n(n-1)}{2}, 400\Big)$ — 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 \le x, y \le n$, $1 \le w \le 10^9$, $x \ne 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-----
Input
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

Output
3

Input
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

Output
9

Difficulty: HARD
Tags: Complete search

Sorting

Shortest paths

Constructive algorithms
Skill types: Sorting

Complete search

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(N, M, K) = list(map(int, input().split()))
X = []
for _ in range(M):
	(x, y, w) = list(map(int, input().split()))
	X.append([min(x, y), max(x, y), w])
X = (sorted(X, key=lambda x: x[2]) + [[0, 0, 10 ** 20] for _ in range(K)])[:K]
D = {}
for (x, y, w) in X:
	if x:
		D[x * 10 ** 6 + y] = w
flg = 1
while flg:
	flg = 0
	for i in range(len(X)):
		(x1, y1, w1) = X[i]
		for j in range(i + 1, len(X)):
			(x2, y2, w2) = X[j]
			if x1 == x2:
				(a, b) = (min(y1, y2), max(y1, y2))
			elif y1 == y2:
				(a, b) = (min(x1, x2), max(x1, x2))
			elif x1 == y2:
				(a, b) = (x2, y1)
			elif x2 == y1:
				(a, b) = (x1, y2)
			else:
				(a, b) = (0, 0)
			if a:
				if a * 10 ** 6 + b in D and w1 + w2 < D[a * 10 ** 6 + b] or (a * 10 ** 6 + b not in D and w1 + w2 < X[-1][2]):
					if a * 10 ** 6 + b in D:
						for k in range(len(X)):
							if X[k][0] == a and X[k][1] == b:
								X[k][2] = w1 + w2
					else:
						(x, y, w) = X.pop()
						if x:
							D.pop(x * 10 ** 6 + y)
						X.append([a, b, w1 + w2])
					D[a * 10 ** 6 + b] = w1 + w2
					X = sorted(X, key=lambda x: x[2])
					flg = 1
					break
		if flg:
			break
print(X[-1][2])


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
(n, m, k) = inpl()
edges = [inpl() for _ in range(m)]
edges.sort(key=lambda x: x[2])
edges = edges[:min(m, k)]
se = set()
for (a, b, _) in edges:
	se.add(a - 1)
	se.add(b - 1)
ls = list(se)
ls.sort()
ln = len(ls)
d = {}
for (i, x) in enumerate(ls):
	d[x] = i
g = [[] for _ in range(ln)]

def dijkstra(s):
	d = [INF] * ln
	d[s] = 0
	edge = []
	heappush(edge, (0, s))
	while edge:
		(mi_cost, mi_to) = heappop(edge)
		if d[mi_to] < mi_cost:
			continue
		for (cost, to) in g[mi_to]:
			if d[to] <= mi_cost + cost:
				continue
			d[to] = mi_cost + cost
			heappush(edge, (cost + mi_cost, to))
	return d
for (a, b, w) in edges:
	(A, B) = (d[a - 1], d[b - 1])
	g[A].append((w, B))
	g[B].append((w, A))
dist = defaultdict(int)
for i in range(ln):
	for x in dijkstra(i):
		dist[x] += 1
cnt = 0
for key in sorted(dist.keys())[1:]:
	cnt += dist[key] // 2
	if cnt >= k:
		err(key)


import sys
input = sys.stdin.readline
(n, m, k) = list(map(int, input().split()))
EDGE = [list(map(int, input().split())) for i in range(m)]
EDGE.sort(key=lambda x: x[2])
EDGE = EDGE[:k]
COST_vertex = [[] for i in range(n + 1)]
VERLIST = []
for (a, b, c) in EDGE:
	COST_vertex[a].append((b, c))
	COST_vertex[b].append((a, c))
	VERLIST.append(a)
	VERLIST.append(b)
VERLIST = sorted(set(VERLIST))
import heapq
ANS = [-1 << 50] * k
for start in VERLIST:
	MINCOST = [1 << 50] * (n + 1)
	checking = [(0, start)]
	MINCOST[start] = 0
	j = 0
	while j < k:
		if not checking:
			break
		(cost, checktown) = heapq.heappop(checking)
		if cost >= -ANS[0]:
			break
		if MINCOST[checktown] < cost:
			continue
		if cost != 0 and checktown > start:
			heapq.heappop(ANS)
			heapq.heappush(ANS, -cost)
			j += 1
		for (to, co) in COST_vertex[checktown]:
			if MINCOST[to] > cost + co:
				MINCOST[to] = cost + co
				heapq.heappush(checking, (cost + co, to))
print(-ANS[0])


import heapq
(n, m, k) = list(map(int, input().split()))
connectionList = []
for _ in range(n):
	connectionList.append([])
edgeList = []
for _ in range(m):
	(x, y, w) = list(map(int, input().split()))
	edgeList.append((x, y, w))
edgeList.sort(key=lambda x: x[2])
if k < m:
	maxDist = edgeList[min(m, k) - 1][2]
else:
	maxDist = sum([x[2] for x in edgeList])
colorList = {}
colorVertex = []
for i in range(n):
	colorList[i] = [i]
	colorVertex.append(i)
for i in range(min(m, k)):
	(x, y, w) = edgeList[i]
	connectionList[x - 1].append((y - 1, w))
	connectionList[y - 1].append((x - 1, w))
	if colorVertex[x - 1] != colorVertex[y - 1]:
		if len(colorList[colorVertex[x - 1]]) >= len(colorList[colorVertex[y - 1]]):
			prevColor = colorVertex[y - 1]
			for elem in colorList[colorVertex[y - 1]]:
				colorVertex[elem] = colorVertex[x - 1]
				colorList[colorVertex[x - 1]].append(elem)
			del colorList[prevColor]
		else:
			prevColor = colorVertex[x - 1]
			for elem in colorList[colorVertex[x - 1]]:
				colorVertex[elem] = colorVertex[y - 1]
				colorList[colorVertex[y - 1]].append(elem)
			del colorList[prevColor]
pathList = []
for key in colorList:
	vertexList = colorList[key]
	for mainVertex in vertexList:
		vertexPQueue = []
		isCovered = {}
		distanceDic = {}
		for elem in vertexList:
			isCovered[elem] = False
			distanceDic[elem] = maxDist
		isCovered[mainVertex] = True
		for elem in connectionList[mainVertex]:
			heapq.heappush(vertexPQueue, (elem[1], elem[0]))
			distanceDic[elem[0]] = elem[1]
		while vertexPQueue:
			(distance, curVertex) = heapq.heappop(vertexPQueue)
			if isCovered[curVertex]:
				continue
			elif distance >= maxDist:
				break
			for elem in connectionList[curVertex]:
				if distance + elem[1] < distanceDic[elem[0]]:
					heapq.heappush(vertexPQueue, (distance + elem[1], elem[0]))
					distanceDic[elem[0]] = distance + elem[1]
		for key in distanceDic:
			if distanceDic[key] <= maxDist and key > mainVertex:
				pathList.append(distanceDic[key])
		if len(pathList) > k:
			pathList.sort()
			pathList = pathList[0:k]
			if pathList[-1] < maxDist:
				maxDist = pathList[-1]
pathList.sort()
print(pathList[k - 1])


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(m)]
EDGE.sort(key=lambda x: x[2])
EDGE = EDGE[:k]
COST_vertex = [[] for i in range(n + 1)]
for (a, b, c) in EDGE:
	COST_vertex[a].append((b, c))
	COST_vertex[b].append((a, c))
for i in range(min(m, k)):
	(x, y, c) = EDGE[i]
	EDGE[i] = (c, x, y)
USED_SET = set()
ANS = [-1 << 50] * k
import heapq
while EDGE:
	(c, x, y) = heapq.heappop(EDGE)
	if (x, y) in USED_SET or c >= -ANS[0]:
		continue
	else:
		heapq.heappop(ANS)
		heapq.heappush(ANS, -c)
		USED_SET.add((x, y))
		USED_SET.add((y, x))
	for (to, cost) in COST_vertex[x]:
		if to != y and (not (y, to) in USED_SET) and (c + cost < -ANS[0]):
			heapq.heappush(EDGE, (c + cost, y, to))
	for (to, cost) in COST_vertex[y]:
		if to != x and (not (x, to) in USED_SET) and (c + cost < -ANS[0]):
			heapq.heappush(EDGE, (c + cost, x, to))
print(-ANS[0])