401943: GYM100589 K Police Catching Thief

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Police Catching Thieftime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

A thief is trying to escape the holds of the police through a city. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and M edges.

Thief is currently at vertex numbered S and needs to reach vertex numbered D. Thief moves with constant speed VT = 1.

K policemen are initially located in K distinct locations denoted by A1, A2, ..., AK. Each policeman has a constant speed of VP = 1.

To help policemen, a single power booster have been provided to them. This power booster can be availed once from any one of the Q distinct ‘special’ nodes B1, B2, ..., BQ. Property of this power booster being that it doubles the speed of the policeman who avails this power booster.

Note: A policeman can choose not to avail the power booster even if he is at a ‘special’ node.

You have to print the shortest time in which thief can escape the police regardless of whatever path the police might take. If he can’t reach the destination, output  - 1.

Input

First line contains N and M, the number of nodes and number of edges respectively.

Each of the next M lines contain integers u v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge. Next line contains a single integer K denoting number of different policemen. Next line contains K space separated integers denoting the distinct locations A1, A2, ..., AK.

Next line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B1, B2, ..., BQ.

Next line contains two distinct integers S and D denoting the source and destination of the thief.

Output

For each test case print the minimum time required for thief to escape(if possible). Else, output  - 1.

Constraints

  • 1  ≤  N  ≤  105
  • M  ≤  min(2 * 105, N * (N - 1) / 2)
  • 0  ≤  u, v, S, D, Ai, Bi < N
  • 0  ≤  Y  ≤  109
  • 1  ≤  X, u, v  ≤  N
  • 0  ≤  K, Q  ≤  N
  • 1  ≤  w  ≤  109
ExamplesInput
4 4
0 1 2
1 2 4
2 3 10
3 0 2
1
3
1
0
2 1
Output
-1
Input
4 3
0 1 2
1 2 8
1 3 10
2
2 3
2
2 3
0 1
Output
2
Note

Example1:

Police takes the path 3 to 0 to 1 availing the power booster at node 0. Even though both policeman and thief reach the destination at same time, police catches thief.

Example2:

Whichever policeman uses the power booster, thief will be able to escape in 2 seconds.

加入题单

上一题 下一题 算法标签: