第K短路径

提交数: 124, 通过率: 35.48%, 平均分: 36.13

题目描述:

一个有向图有n个点,m条边,给出起点s和终点t,求从s到t的第k短路的长度,路径允许重复经过点或边。

输入格式:

第一行,包括两个整数n、m。结点编号依次从1到n编号。

接下来m行,每行包含3个整数 A, B 和 T (1 <= A, B <= N, 1 <= T <= 100),表示从A点到B点长度为T。

最后一行包括三个整数 S, T 和 K (1 <= S, T <= N, 1 <= K <= 1000)。

输出格式:

一个整数,表示第k短的路径长度,如果不存在,输出-1。

样例输入:

2 2
1 2 5
2 1 4
1 2 2

样例输出:

14

提示:

1 <= N <= 1000, 0 <= M <= 100000

1 <= S, T <= N, 1 <= K <= 1000

时间限制: 1000ms
空间限制: 256MB