P13866 [SWERC 2020] Daisy 的迷宫

:::align{center}  ::: Daisy 喜欢在迷宫中散步，以缓解漫长工作日带来的压力。她喜欢的迷宫都由一组房间组成，有一个入口房间和一个出口房间，每个房间中有若干扇单向门通往其他房间。Daisy 的目标是找到一条从入口到出口的路径。 Daisy 有一套解迷宫的方法。她注意到，每个房间中不同的门颜色不同，因此她可以通过记录路径上门的颜色来记住自己走过的路线。为此，她在进入迷宫之前查看平面图，并构建一副由彩色卡片组成的牌堆，牌堆中的卡片颜色对应她需要依次经过的门的颜色。每当她进入一个房间时，她就从牌堆顶部取出一张卡片，然后走颜色与这张卡片相同的门，之后丢弃这张卡片。 有时 Daisy 的牌堆是"不完整的"，她会到达一个房间时发现牌堆为空，或者顶部的卡片颜色对应不上房间中的任何一扇门。在这种情况下，Daisy 会选择房间中的一扇门通过，并且不是丢弃顶部的卡片，而是在牌堆顶部添加一张她所经过的门的颜色的卡片。 让我们考虑以下例子：一个有三个房间和三扇门的迷宫，一扇红色的门从入口通向房间 1，第二扇红色的门从房间 1 返回入口，以及一扇蓝色的门连接房间 1 和出口。在这个示例迷宫（如下图所示）中： - 如果 Daisy 开始时牌堆顶部是一张**红色**卡片，下面是一张**蓝色**卡片，她会先走到房间 1 并丢弃红色卡片，然后走到出口并丢弃蓝色卡片； - 如果 Daisy 开始时牌堆只有一张**红色**卡片，那么她第一步必然走到房间 1，丢弃红色卡片，然后她可以选择走**蓝色**门离开（最后牌堆是否为空无关紧要），或者她也可以选择走红色门，回到初始状态：在入口房间且牌堆中只有一张红色卡片； - 如果她在入口房间时牌堆为空，无论是开始时还是后来到达时，她必然会无限循环。因为入口只有一扇门通往房间 1。一旦她到达房间 1，她的牌堆顶部有一张*红色*卡片，因此她必须走*红色*门并丢弃这张卡片，这会使她回到入口房间且牌堆为空。 :::align{center}  ::: Daisy 知道，在她所有的迷宫中，只要选择合适的牌堆，她总能从入口房间到达出口房间。然而，有些牌堆无论她如何选择都无法逃脱。她想知道：能让她逃脱的牌堆的最小大小是多少？Daisy 把迷宫平面图交给你，请你帮她确定，在做出正确选择的前提下，能使她从入口房间到达出口房间的牌堆的最小大小。

第一行包含三个整数 $R$、$D$ 和 $C$，用空格分隔。$R$ 是房间数量，$D$ 是门的数量，$C$ 是颜色数量。房间编号为 $0$ 到 $R-1$，颜色编号为 $0$ 到 $C-1$。 接下来的 $D$ 行，每行描述一扇门，包含三个整数 $f$、$t$ 和 $c$，用空格分隔，满足 $0 \leq f \leq R-1$，$0 \leq t \leq R-1$，$f \neq t$，$0 \leq c \leq C-1$。这表示有一扇从房间 $f$ 到房间 $t$ 的门，该门的颜色为 $c$。

输出应包含一行一个整数：最小的整数 $S$，使得存在一副由 $S$ 张卡片组成的牌堆，能够让 Daisy 在做出正确选择的前提下，从入口（编号为 $0$ 的房间）到达出口（编号为 $R-1$ 的房间）。

**限制条件** - $2 \leq R \leq 50$； - $2 \leq D \leq 100$； - $2 \leq C \leq 20$。 **样例解释 1** - Daisy 从房间 0 开始，牌堆为空； - 她走到房间 1，牌堆顶部多了一张颜色为 $\textbf{0}$ 的卡片； - 她走到房间 2，牌堆为空； - 她走到房间 0，牌堆顶部多了一张颜色为 $\textbf{0}$ 的卡片； - 她走到房间 1，牌堆为空； - 此时她可以选择去往出口。 **样例解释 2** 这个例子对应正文中描述的那个例子，其中红色表示为 1，蓝色表示为 0。 --- 由 Deepseek V4 初步翻译，人工修缮。