#72. 第K短路

第K短路

给定一张N个点(编号1,2…N),M条边的有向图,求从起点S到终点T的第K短路的长度,路径允许重复经过点或边。

注意: 每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数N和M。

接下来M行,每行包含三个整数A,B和L,表示点A与点B之间存在有向边,且边长为L。

最后一行包含三个整数S,T和K,分别表示起点S,终点T和第K短路。

输出格式

输出占一行,包含一个整数,表示第K短路的长度,如果第K短路不存在,则输出“-1”。

数据范围

1S,TN10001 \le S,T \le N \le 1000,
0M1050 \le M \le 10^5,
1K10001 \le K \le 1000,
1L1001 \le L \le 100

输入样例:

2 2
1 2 5
2 1 4
1 2 2

输出样例:

14

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解