Description

Wonder City is a beautiful place and has attracted a considerable amount of tourists in these years. The mayor is planning to build a new airport to accommodate tourists. The new airport will provide free shuttle buses to all hotels in Wonder City. There are several tourist centers. In order to further introduce the beauty of this city to tourists, each shuttle bus will first stop by a tourist center before arriving at its destination hotel.

With the existence of hotels and tourist centers, the mayor wants to find the best location for the new airport. In what follows, let G = (V, E) be an undirected connected graph representing the map of Wonder City, where V is the vertex set and E is the edge set. In this problem, we consider each edge as a line segment in the Euclidean plane so that we can talk about points, not necessarily vertices, on the edges. We also use G to denote the set of all points of the graph. Thus, the notation x  G means that x is a point along any edge ofG which may or may not be a vertex of G. Each edge e  E has a nonnegative integral length. For any two points a, b  G, let d (a, b)be the distance of the shortest path between a and b. For example, in Figure 3, d (p, h₂) = 20.75 and d (c_a, c_b) = 29. Let C  V denote the set of tourist centers and let H  V denote the set of hotels. The mayor's strategy for choosing the location of the airport is as follows.

 

1. Any point of G can be selected as the new airport p.
2. The shuttle bus to each hotel h  H will stop by the tourist center c  C that minimizes the distance d (p, c) + d (c, h), so that tourists can arrive at their hotels as soon as possible.
3. For each h  H, let s(p, h) = min{d (p, c) + d (c, h)| c  C} and t(h) be the expected number of tourists from the airport to the hotel h every day. The new airport should minimize the largest unsatisfactory factor f (p) = max{t(h) x s(p, h)| h  H}. (In this scenario a hotel h is considered more important than another hotel h' if t(h) > t(h').)

Consider the example in Figure 3. Suppose the airport p is built at location h₃. Then, s(p, h₁) = min{d (p, c_a) + d (c_a, h₁), d (p, c_b) + d(c_b, h₁)} = min{34, 52} = 34. Similarly, we have s(p, h₂) = 28 and s(p, h₃) = 26. Therefore, the largest unsatisfactory factor is f (p) = max{30 x 34, 50 x 28, 20 x 26} = 1400. In this example, the best location of p is on the edge (h₃, c_b), which is 4.75 units of distance away from h₃ and 8.25 units of distance away from c_b. The largest unsatisfactory factor of this location is f (p) = 1162.5.

 

 

Please help the mayor of Wonder City to determine the best location of the new airport. For simplicity, only the largest unsatisfactory factor of the new airport is required.

 

Technical Specification

 

1. The number of hotels, n = | H| : 2n200.
2. The number of tourist centers, k = | C| : 2k30.
3. The number of edges, m = | E| : 3m8000.
4. The expected number of tourists for each hotel h, t(h) : 1t(h)100.
5. CH =  and the vertex set is V = CH.
6. There is at most one undirected edge between any pair of vertices.

Input

There are at most 10 test cases. The first line of each test case consists of the three integers n, k, and m. Denote the n hotels by v₁, v₂,...,v_n; and denote the k tourist centers by v_n+1, v_n+2,..., v_n+k. Next, m lines follow. Each line contains three integers i, j, l, where 1i  jn + k and 0l1000000, indicating that there is an edge of length l connecting v_i and v_j. Finally, there is a line containing the nintegers t(v₁), t(v₂), ..., t(v_n). The last test case will be followed by a line consisting of n = k = m = 0.

Output

For each test case, print a line containing the largest unsatisfactory factor of the new airport, rounded to three decimal places. Use the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss