K-th Path (Codeforces 1196F)
Tags: Others, shortest paths

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).


Sample Inputs:
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

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

Sample Outputs:
3

9

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from heapq import heappop, heappush, heapify
input = sys.stdin.readline

def dijkstra(s):
    dis = [10 ** 15] * len(node)
    dis[s] = 0
    path = []
    heappush(path, (s, 0))
    while path:
        (u, sum_cost) = heappop(path)
        if dis[u] < sum_cost:
            continue
        for (v, cost) in g[u]:
            if dis[v] <= sum_cost + cost:
                continue
            dis[v] = sum_cost + cost
            heappush(path, (v, sum_cost + cost))
    return dis
(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[:min(m, k)]
node = set()
for (u, v, w) in edge:
    node.add(u - 1)
    node.add(v - 1)
node = list(node)
node.sort()
d = {}
for (i, u) in enumerate(node):
    d[u] = i
g = [[] for i in range(len(node))]
for (u, v, w) in edge:
    (x, y) = (d[u - 1], d[v - 1])
    g[x].append((y, w))
    g[y].append((x, w))
dist = defaultdict(int)
for i in range(len(node)):
    for u in dijkstra(i):
        dist[u] += 1
count = 0
for key in sorted(dist.keys())[1:]:
    count += dist[key] // 2
    if count >= k:
        print(key)
        exit()

Solution (Python):
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)

Solution (Python):
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
    seen = [False] * n
    seen[s] = True
    edge = []
    for x in g[s]:
        heappush(edge, x)
    while edge:
        (mi_cost, mi_to) = heappop(edge)
        if seen[mi_to]:
            continue
        d[mi_to] = mi_cost
        seen[mi_to] = True
        for (cost, to) in g[mi_to]:
            if d[to] <= mi_cost + cost:
                continue
            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)