Locks and keys

时间限制:5s    【提交】    空间限制:128MB


A wizard is in a labyrinth where there are V rooms and V - 1 doors connecting some pairs of rooms in both directions, in such a way that there is always a sequence of doors one can traverse to go from a room to any other room. Additionally, there are C locks and C keys of C different colours (one of each) in some of the doors and rooms of the maze, respectively; each door has at most one lock, and there is at most one key placed in each room. It should be an easy matter for the wizard to bypass the lock system, were it not for the fact that he forgot his spell book, without which his wizardry is utterly useless. The wizard is currently in room X, and he wants to get his spell book, located in room Y, without taking too long. At every step he may go to an adjacent room through one of the doors. Of course, if the door is locked, he needs to be carrying the key of the same colour as the lock (unless, of course, that door has already been unlocked). The wizard can carry only one key at a time and after picking up a key it is not possible for him to drop it somewhere in the maze in order to take it again afterwards. Once a door has been unlocked, the key is thrown away since it is no longer any use.

Given the maze and the positions of the C keys and C locks, determine how to reach Y from X, if possible. Any path whose length does not exceed 4 . (C + 1) . V is acceptable.

The first line of each case contains four integers: the number V of rooms in the maze ( 1<=V<=1 500), the number C of locks ( 0<=C< V), and rooms X and Y numbered 0, 1,..., V - 1. Then comes a (possibly empty) line with C integers indicating the location of each of the keys, in order of increasing colour. The next V - 1 lines describe the maze: each contains three integers A B L, meaning that there is a door between rooms A and B which can be unlocked with the key of colour L, if 0<=L < C; a value of -1 for L indicates that no lock is needed.

The last line has V, C, X, Y = 0, 0, 0, 0.



给出迷宫的形态和C个钥匙和C个锁的位置。如果可以从XY,请给出方案。任何一个不超过4 *(C + 1) * V的方案都是可以被接受的(囧啊。。。。)












1 0 0 0

3 1 0 2
0 1 -1
0 2 0

3 2 0 2
1 2
0 1 1
0 2 0

5 3 0 4
2 0 3
0 1 0
0 2 -1
1 3 1
2 4 2

0 0 0 0


0: 0
3: 0 1 0 2
10: 0 2 0 1 0 1 3 1 0 2 4