#993. 【模板】k 短路

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mars_Dingdang

题目描述

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

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

题目来源:AcWing

题解:搜索优化

输入格式

第一行包含两个整数 N M

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

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

输出格式

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

样例

输入:

2 2
1 2 5
2 1 4
1 2 2

输出:

14

数据范围与提示

1≤S,T≤N≤1000 , 0≤M≤10^5 , 1≤K≤1000 , 1≤L≤1000