2455 - K短路
题目描述
有 n 个城市和 m 条单向道路，城市编号为 1 到 n。
给定两个城市 a 和 b，请求出从 a 城市到 b 城市的第k 短路的长度。（允许经过重复的点或者边）
输入
第一行有四个整数 n , m , a , b , k。(1≤n≤1000 , 0≤m≤10000 , 1≤a,b≤n , a \neq b , 1≤k≤1000)。
接下来 m 行，每行有3个整数 x,y,l，表示 x 到 y 之间有一条长为 l 的道路。（1≤x,y≤n,1≤l≤100）。
输出
输出第 k 短路的长度，不存在第 k 短路，请输出 -1 。
样例
输入
3 3 1 3 2 1 2 1 2 3 1 1 3 2
输出
2
来源
POJ
标签
