Processing math: 100%
编程题
                k短路

题目描述

n 个城市和 m 条单向道路,城市编号为 1n。每条道路连接两个不同的城市,且任意两条道路要么起点不同要么终点不同,因此 nm 满足mn(n1)

给定两个城市 ab,可以给 ab 的所有简单路(所有城市最多经过一次,包括起点和终点)排序:先按长度从小到大排序,长度相同时按照字典序从小到大排序。你的任务是求出 ab 的第 k 短路。

输入描述

输入第一行包含五个正整数 nmkab

以下 m 行每行三个整数 uvl,表示从城市 u 到城市 v 有一条长度为 l 的单向道路。

其中,2n501k200

输出描述

如果 ab 的简单路不足 k 条,输出 No,否则输出第 k 短路:从城市 a 开始依次输出每个到达的城市,直到城市 b,中间用减号 - 分割。

输入输出样例

示例 1

>输入

4 6 1 1 4
2 4 2
1 3 2
1 2 1
1 4 3
2 3 1
3 4 1

>输出

1-2-3-4

示例 2

>输入

3 3 5 1 3
1 2 1
2 3 1
1 3 1

>输出

No
查看答案
赣ICP备20007335号-2