zmeu
The Dragon has locked up the Emperor's 5 daughters in his castle. Prince Charming has come to get them out of the castle, using the map the Good Fairy gave him. The map contains the castle's n rooms, numbered from 1 to n and the m tunnels between rooms. Also marked are the rooms where the girls and Prince Charming are, the time needed to cross each tunnel and the p rooms through which they can exit the castle.
Task
Determine the minimum amount of time needed by Prince Charming to get to the 5 girls and get them out of the castle.
Input data
The first line of input file
zmeu.in contains 3 numbers
n, m and p, representing the number of rooms,
number of tunnels and, respectively, the number of castle exits.
The second
line contains the numbers of 6 different rooms: the first number is the room in
which Prince Charming is in, and the other five the rooms where the girls are.
The following m lines contain
3 numbers each, representing the m tunnels: the first two represent the
rooms the tunnel connects and the third the time needed to cross the tunnel.
The last p lines contain a
number each, representing the rooms through which one can exit the castle. All
numbers are positive integers, and numbers located on the same line are
separated by a space.
Output data
The first line of file zmeu.out will contain a single line with a single number, the minimum time needed to start from Prince Charming's room, going through the rooms of the 5 girls and getting to a room that connects to the outside. Only time needed to cross tunnels will be taken into consideration; the amount of time required to cross rooms or exit the castle will be ignored.
Constraints
Example
zmeu.in |
zmeu.out |
Explanation |
10 11 3 |
29 |
A possible route is: 2-1-7-1-2-3-5-3-6-10-6-3-4 |
Time limit: 1 second/test
prof. Nistor Mot
Braila "N.Balcescu" National High
School
mailto:emotz_ro@yahoo.co.uk