Landline Telephone Network


The mayor of RMRCity wants to create a secure landline telephone network for emergency use in case of serious disasters when the city is cut off from the outside world. Some pairs of buildings in the city can be directly connected with a wire telephone line and the municipality engineers have prepared an estimate of the cost of connecting any such pair.

The mayor needs your help to find the cheapest network that connects all buildings in the city and satisfies a particular security measure that will be explained shortly. A call from a building $A$ to another building $B$ may be routed through any simple path in the network (i.e., a path that does not have any repeated building). There are also some insecure buildings that one or more persons with serious criminal records live in. The mayor wants only communications intended for these insecure buildings to reach them. In other words, no communication from any building $A$ to any building $B$ should pass through any insecure building $C$ in the network (where $C$ is different from $A$ and $B$).


The input consists of a single test case. The first line contains three integers $n$, $m$, $p$ where $1 \le n \le 1\, 000$ is the number of buildings, $0 \le m \le 100\, 000$ is the number of possible direct connections between a pair of buildings, and $0 \le p \le n$ is the number of insecure buildings. The buildings are numbered from $1$ to $n$. The second line contains $p$ distinct integers between $1$ and $n$ (inclusive), which are the numbers of insecure buildings. Each of the next $m$ lines contains three integers $x_ i$, $y_ i$, and $\ell _ i$ describing one potential direct line, where $x_ i$ and $y_ i$ $(1 \le x_ i, y_ i \le n)$ are the distinct buildings the line connects, and $\ell _ i$ $(1 \le \ell _ i \le 10\, 000)$ is the estimate of the cost of connecting these buildings. There is at most one direct link between any two buildings in these $m$ lines.


Display the cost of the cheapest network satisfying the security measure if it is possible. Otherwise, display impossible.

Sample Input 1 Sample Output 1
4 6 1
1 2 1
1 3 1
1 4 1
2 3 2
2 4 4
3 4 3
Sample Input 2 Sample Output 2
4 3 2
1 2
1 2 1
2 3 7
3 4 5
CPU Time limit 4 seconds
Memory limit 1024 MB
Difficulty 5.5hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in