SP3941 MKTHPATH - Kth Shortest Path

Isaac 对于每天使用相同的最短路线去上班感到十分厌烦。尽管这样做可以节省时间，他却不得不反复欣赏相同的风景，这让他难以忍受。 某天，他决定对这种情况进行一些改变。他计划每天至少对路线做一些细微的调整。具体来说，第一天他将走最短的路线；第二天，他会选择第二短的路线，也就是不使用第一天选择的那条。更一般地，在第 $k$ 天，他会选择第 $k$ 短的路线。当然，路线中不允许重复经过同一地点。 你需要帮助 Isaac，为他编写一个程序来找出他在第 $k$ 天应走的路线。这个问题可以用图论来建模。你的程序需要在给定的有向图中找出从起点到终点的第 $k$ 短路径。

输入包括多个数据集，每个数据集的格式如下： ``` n m k a b x1 y1 d1 x2 y2 d2 … xm ym dm ``` 每行中的多个输入项是用空格分隔的非负整数。 - $n$ 表示图中的节点数，$2 \le n \le 100$。 - $m$ 表示图中的边数，$1 \le m \le 1000$。 - $k$ 表示要找到的路径序号，$1 \le k \le 10000$。 - $a$ 和 $b$ 分别表示起点和终点，$1 \le a, b \le n$ 且 $a \neq b$。 - 每条边由三个整数 $x_i, y_i, d_i$ 组成，分别表示这条边的起点、终点和长度，$1 \le x_i, y_i \le n$ 且 $1 \le d_i \le 10000$。

对于每个输入数据集，输出一行。输出行不应包含多余的字符如空格。 - 如果从 $a$ 到 $b$ 的不同路径少于 $k$ 条，输出 "None"。注意 "None" 的首字母大写。 - 如果从 $a$ 到 $b$ 的不同路径不少于 $k$ 条，输出第 $k$ 短路径上的节点编号，并按访问顺序用连字符（-）分隔。注意，第一个节点必须是 $a$，最后一个节点必须是 $b$。 在这个问题中，“更短”有特殊的含义：路径 $P$ 比路径 $Q$ 更短，当且仅当以下任一条件成立： 1. 路径 $P$ 的总长度小于路径 $Q$。 2. 两条路径长度相等，但路径 $P$ 的节点序列在字典序中小于路径 $Q$。具体来说，设 $P$ 的节点序列为 $p_1, p_2, \ldots, p_s$，$Q$ 的节点序列为 $q_1, q_2, \ldots, q_t$。两条路径都必须从 $a$ 起始，以 $b$ 结束。在字典序中，若存在某个 $r (1 \le r < s)$ 使得 $p_1 = q_1, p_2 = q_2, \ldots, p_{r-1} = q_{r-1}$ 且 $p_r < q_r$，则路径 $P$ 比路径 $Q$ 更短。 **本翻译由 AI 自动生成**