시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 42 | 14 | 13 | 31.707% |
Daisy enjoys walking in mazes to evacuate the stress of a long day of work. The mazes that she likes are all composed of a set of rooms with one entry room, one exit room, and in each room there are several one-way doors leading to other rooms. Daisy's goal is to find a path from the entry to the exit.
Daisy has a technique to solve mazes. She has noticed that the different doors of any room have different colors and thus she can remember her path by keeping track of the colors of doors along her path. For that, she looks at the plan before entering the maze and builds a deck of colored cards corresponding to the colors of doors she needs to take. Whenever she enters a room, she goes through the door that has the color of the topmost card in her deck and then she discards this card.
It sometimes happens that Daisy's decks are "incomplete" and she arrives in a room with an empty deck or with a topmost card that has a color corresponding to none of the doors. In those cases, Daisy goes through one of the doors in the room and, instead of discarding the topmost card, she adds on top of her deck a card of the color of the door she took.
Let us consider the following example maze with three rooms and three doors: a red door from the entry to room 1, a second red door from room 1 back to the entry, and a blue door between room 1 and the exit. In this example maze (also depicted below) then:
Daisy knows that, in all of her labyrinths, she can always go from the entry room to the exit room with the right deck. However, some decks do not allow her to escape, whatever the choices she may ever do. She wonders: what is the minimal size of a deck that allows her to escape? Daisy gives you the plan of the maze and asks you to help her determine the minimal size of a deck that allows her go from the entry room to the exit if she makes the right choices.
The first line contains three integers $R$, $D$, and $C$, separated by spaces. $R$ is the number of rooms, $D$ is the number of doors, and $C$ is the number of colors. Rooms are numbered from $0$ to $R-1$, and colors are numbered from $0$ to $C-1$.
The next $D$ lines each describes a door with three integers $f$, $t$ and $c$, separated by spaces, and such that $0\leq f \leq R-1$, $0 \leq t \leq R-1$, $f\neq t$, and $0\leq c \leq C-1$. This indicates that there is a door from room $f$ to room $t$, and that this door has color $c$.
The output should contain a single line with a single integer: the minimal integer $S$ such that there is a deck composed of $S$ cards that allows Daisy, if she makes the right choices, to go from the entry (the room numbered $0$) to the exit (the room numbered $R-1$).
4 4 2 0 1 0 1 2 0 2 0 0 1 3 1
0
3 3 2 0 1 1 1 0 1 1 2 0
1
This example corresponds to the one given in the text with red represented as 1 and blue as 0.
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2020-2021 J번