← 返回题目列表

Codeforces · 1196/F

F. 第 K 条路径

中文机器翻译题面 查看原题

给您一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的连通无向加权图。

您需要打印该图中第 $$$k$$$ 最小的最短路径(从顶点到自身的路径不计算在内,从 $$$i$$$ 到 $$$j$$$ 和从 $$$j$$$ 到 $$$i$$$ 的路径算作 1)。

更正式地说,如果 $$$d$$$ 是最短路径矩阵,其中 $$$d_{i, j}$$$ 是顶点 $$$i$$$ 和 $$$j$$$ 之间的最短路径的长度 ($$$1 \le i < j \le n$$$),那么您需要打印由所有组成的排序数组中的第 $$$k$$$ 个元素$$$d_{i, j}$$$,其中 $$$1 \le i < j \le n$$$。

输入

输入的第一行包含三个整数 $$$n、m$$$ 和 $$$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)$$$ — 图中的顶点数、图中的边数以及 $$$k$$$ 的值。

接下来是 $$$m$$$ 行,每行包含三个整数 $$$x$$$、$$$y$$$ 和 $$$w$$$ ($$$1 \le x, y \le n$$$, $$$1 \le w \le 10^9$$$, $$$x \ne y$$$) 表示顶点 $$$x$$$ 和$$$y$$$ 重量 $$$w$$$。

保证给定的图是连通的(任意一对顶点之间有路径),不存在自环(连接顶点与自身的边)和多条边(对于每对顶点 $$$x$$$ 和 $$$y$$$,图中这对顶点之间至多有一条边)。

输出

打印一个整数 - 给定图中第 $$$k$$$ 最短路径的长度(从顶点到自身的路径不计算在内,从 $$$i$$$ 到 $$$j$$$ 和从 $$$j$$$ 到 $$$i$$$ 的路径计为 1)。

示例

输入 #1

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

输出 #1

3

输入 #2

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

输出 #2

9