3039. 第K短路
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 给定一张 $N$ 个点（编号 $1,2\dotsN$），$M$ 条边的有向图，求从起点 $S$ 到终点$T$ 的第 $K$ 短路的长度，路径允许重复经过点或边。 ## 注意 每条最短路中至少要包含一条边。 ## 输入格式 第一行包含两个整数 $N$ 和 $M$。 接下来 $M$行，每行包含三个整数 $A,B$ 和 $L$，表示点 $A$ 与点 $B$ 之间存在有向边，且边长为 $L$。 最后一行包含三个整数 $S,T$ 和 $K$，分别表示起点 $S$，终点 $T$ 和第 $K$ 短路。 ## 输出格式 输出占一行，包含一个整数，表示第 $K$ 短路的长度，如果第 $K$ 短路不存在，则输出 $-1$。 ## 输入 ```in1 2 2 1 2 5 2 1 4 1 2 2 ``` ## 输出 ```out1 14 ``` ## 提示