CAPRICA - Caprica Cities

no tags 

Caprica is one of the 12 colonial planets, but it was completely destroyed by the cylons, robots made by humans that had rebelled. Before the attack, Doctor Gaius Baltar had the following problem. Caprica has N cities, numbered from 0 to N − 1, and M bidirectional roads connecting them, in a way that exists a path between every pair of cities. Let X and Y be two disjoint and non-empty subsets of this N cities. The problem is to find the smallest path length between any cities x and y where x ∈ X and y ∈ Y. A path length is the sum of the distance of each road in this path.

Input

Each test case is described using several lines. The first line contains four integers N, M, A and B representing respectively the number of cities (2 ≤ N ≤ 1000), the number of roads (1 ≤ M ≤ 104), the number of cities in X (2 ≤ A ≤ 1000), and the number of cities in Y (2 ≤ B ≤ 1000), where A + B ≤ N.

The second line contains A integers and the third line contains B integers, representing the cities in X and Y respectively. Each of the next M lines describes a road using three integers, u, v, and d, indicating that there is a road between the cities u and v with distance d (1 ≤ d ≤ 104). The last test case is followed by a line containing four zeros.

Output

For each test case output, in a single line, the integer representing the smallest path length between x and y where x ∈ X and y ∈ Y .

Example

Input:
4 4 2 2
0 1
2 3
0 1 10
0 2 20
1 3 10
2 3 10
0 0 0 0

Output: 10

hide comments
smso: 2020-12-22 10:38:03

One more test case:
6 5 2 2
0 1
4 5
1 3 10
2 4 10
0 2 1
2 3 1
3 5 1
0 0 0 0
output: 3

bfs, beware of duplicated edges!

nadstratosfer: 2020-01-31 20:39:56

Got AC, but a more refined approach assuming X and Y are geographically coherent regions gets WA. Bit of a wasted opportunity here, nice problem nevertheless.

Edit: I take that back, a more refined approach is still possible =)

Last edit: 2020-01-31 20:53:35
hodobox: 2016-06-12 21:23:06

104 -> 10^4

Re(Tjandra): Fixed

Last edit: 2016-06-13 06:52:10
Liquid_Science: 2016-02-20 21:09:05

This is not very easy in java , had to write 3 versions to get within 0.10 secs

Aman Singh: 2015-10-14 20:45:49

How can 104 roads connect 1000 cities?

Rajat (1307086): 2015-07-22 00:19:19

Modified Dijkstra

Walter Erquinigo: 2012-02-09 18:34:26

In portuguese is very clear xd


Added by:Paulo Costa
Date:2012-01-19
Time limit:0.202s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64