k短路 ### 题目描述 有 $n$ 个城市和 $m$ 条单向道路，城市编号为 $1$ 到 $n$。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此 $n$ 和 $m$ 满足$m \le n(n-1)$。 给定两个城市 $a$ 和 $b$，可以给 $a$ 到 $b$ 的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出 $a$ 到 $b$ 的第 $k$ 短路。 ### 输入描述 输入第一行包含五个正整数 $n$，$m$，$k$，$a$，$b$。 以下 $m$ 行每行三个整数 $u$，$v$，$l$，表示从城市 $u$ 到城市 $v$ 有一条长度为 $l$ 的单向道路。 其中，$2\leq n\leq 50$，$1\leq k\leq 200$。 ### 输出描述 如果 $a$ 到 $b$ 的简单路不足 $k$ 条，输出 `No`，否则输出第 $k$ 短路：从城市 $a$ 开始依次输出每个到达的城市，直到城市 $b$，中间用减号 `-` 分割。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 ``` >输出 ```txt 1-2-3-4 ``` #### 示例 2 >输入 ```txt 3 3 5 1 3 1 2 1 2 3 1 1 3 1 ``` >输出 ```txt No ```