A6173. K-th Path
编程题
普及+/提高
知识点
题目描述
给定一个无向带权连通图，求子节点两两之间最短路径长度从小到大排序之后第 $k$ 条路径长度。
输入格式
第一行三个整数 $n,m,k$。共有 $n$ 个结点，$m$ 条**双向**边，求第 $k$ 短的路径。
之后 $m$ 行，每行三个整数 $x,y,w(x\neq y)$，表示 $x,y$ 之间有一条长为 $w$ 的**双向**边。
之后 $m$ 行，每行三个整数 $x,y,w(x\neq y)$，表示 $x,y$ 之间有一条长为 $w$ 的**双向**边。
输出格式
一个整数，即子节点两两之间最短路径长度从小到大排序之后第 $k$ 条路径长度。
输入输出样例
输入 #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
说明/提示
对于 $100\%$ 的数据，$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),1\le w\le 10^9$。