← 返回题目

题库练习 K短路

← 上一题下一题 →

A71388 | $K短路$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

有 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 。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出