Scribd
Upload
14 views2 pages

Lostiks: Inoi 30

Aryo the Brave is navigating a dungeon with N rooms and M locked doors, needing to find the minimum time to travel from room S to room T while collecting keys to unlock doors. Each door can either be unlocked directly if not locked or requires a key located in another room, and Aryo can only carry one key at a time. The document outlines the input format for the dungeon configuration and specifies the output as the minimum time required or -1 if passage is impossible.

Uploaded by

Krishna Kanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views2 pages

Lostiks: Inoi 30

Aryo the Brave is navigating a dungeon with N rooms and M locked doors, needing to find the minimum time to travel from room S to room T while collecting keys to unlock doors. Each door can either be unlocked directly if not locked or requires a key located in another room, and Aryo can only carry one key at a time. The document outlines the input format for the dungeon configuration and specifies the output as the minimum time required or -1 if passage is impossible.

Uploaded by

Krishna Kanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

INOI 30

October – 11 2020
Tehran, Iran LOSTIKS
Summer Camp Programming Finals - Day 2 en (US)

LOSTIKS

Aryo the Brave has bought a new crawler dungeon named Keys. In fact, it’s been days he’s
playing and his army is getting ready for battle without their commander.
Each dungeon of this game has N rooms connected with N − 1 doors together so that their
graph (with nodes equal to rooms and edges equal to doors) is a tree means both connected
and acyclic.

At the start of a dungeon, Aryo is in room S and has to reach room T . The problem is that
M of these doors are locked and their keys can be in some other rooms. And worst Aryo’s
character in the game can carry at most one key at a time means he can’t drop a key till he
hasn’t opened a door with it.
Moving from a room to an adjacent room takes 1 second and taking a key or unlocking a door
takes no time but pay attention that by unlocking a door he won’t move to the other room and
he will just unlock the door.
Aryo’s army needs him but he is stuck in this game, so for each of the dungeons tell him the
minimum time he needs to pass that dungeon so that he can fight alongside his brave soldiers
as soon as possible.

Input

At the first line of input, you get N number of rooms.


next line you get S and T the starting and finishing room.
at next N − 1 lines each line consists of information about a door as u, v, w. u and v are two
rooms connected by the door. if w = 0 door is not locked and else w is the room where the
door’s key is there.

Output

In the only line of the output print a minimum time that Aryo needs to go from S to T . If it’s
not possible to do so print −1.

Constraints
• 1 ≤ n ≤ 106

• 1 ≤ s, t, u, v ≤ n

1 of 3
• 0≤w≤n

• 0 ≤ m ≤ 20

Subtasks

Subtasks score constraints


1 23 n ≤ 100 000, m ≤ 8
2 36 n ≤ 7000
3 41 No additional constraints.

Examples

Standard input Standard output


4 4
1 4
1 2 0
1 3 2
3 4 1
5 10
3 1
1 2 5
2 3 4
3 4 0
4 5 2

2 of 3

You might also like