Reckless Speleologists
InterviewTime limit1sMemory limit1024 MB
Find the fastest route from the start station to the exit, reaching each station strictly before smoke spreading from the campfires does.
- Level
Medium5 of 10
- Topics
- Graph, Shortest path
- Solved
- No attempts yet
Problem
One day a group of speleologists set out to explore the caves of Africa. After going quite deep, they noticed something strange: the air smelled of smoke. "Could we have reached a volcano?" asked a newcomer in surprise. "No. Near a volcano it smells of sulfur," the captain replied. "Who was in charge of putting out the campfires?" Everyone shrugged uncertainly. "Well, friends, we are trapped."
The captain now faces a difficult task: how to lead the team out of the cave without suffocating. In speleologists' terms, a cave consists of many tunnels and stations. Each tunnel connects a pair of different stations and has its own length. The captain has a map of the cave, knows where the team lit campfires, and knows where the exit is.
Smoke spreads 1 meter per second. A tunnel of length adjacent to a smoky station fills with smoke in seconds, and the station at its other end fills with smoke as well. If the speleologists are at a station containing smoke, they suffocate. The speleologists run at 1 meter per second. Tunnels can be traversed in both directions. Initially, smoke is present only at the stations where the speleologists lit campfires. If the speleologists arrive at a station at the same moment the smoke does, they suffocate (this also applies to the exit station). It is guaranteed that the speleologists start at a station with no smoke.
Input
The first line contains three integers , , and : the number of stations, the number of tunnels, and the number of stations with campfires, where , , and . The second line contains distinct integers (), the stations with campfires. Each of the next lines contains three integers , , and , meaning the -th tunnel connects stations and and has length meters, where , , and . The last line contains two integers and (): the station where the speleologists are now, and the station of the exit.
Output
Print one integer, the minimum number of seconds the speleologists need to get out of the cave, or -1 if they cannot get out.