19668번 - Relay Marathon 다국어

You are Nilan, the marathon organiser of the country Berapur. There are N cities in the country, connected by M roads. The cities are indexed from 1, 2, . . . , N each road is indexed from 1, 2, . . . , M. The i^th road directly connects city u_i with city v_i, and it takes w_i seconds to travel on this road. The roads are bidirectional in nature and it is also ensured that there are no selfloops or multi-edges in the road network. Out of the N cities, there is a list of K distinct cities A₁, A₂, . . . , A_k which are special.

As the marathon organiser, you are going to try to organise a relay marathon. A relay marathon is defined as follows: 2 groups of people are present at the starting cities start₁ and start₂ respectively. Firstly the people from start₁ travel to finish₁. Once the first group reaches finish₁, then immediately (i.e without any delay), the second group of people start travelling from start₂ to finish₂. Once the second group reaches finish₂, the relay marathon ends. Do note that a relay marathon is valid only if start₁, finish₁, start₂ and finish₂ all are special and distinct from one another.

Let D(a, b) denote the shortest time to travel from city a to city b in the above road network. In case there is no path from city a to city b, then let us define D(a, b) = ∞. Then the total time taken in such a valid relay race is defined as D(start₁, finish₁) + D(start₂, finish2).

Given this, your job is to find the minimum possible value of D(start₁, finish₁) + D(start₂, finish₂) amongst all valid tuples (start₁, finish₁, start₂, finish₂).

Note: In the input network of roads, it will always be ensured that there are exists at least one valid tuple of four distinct cities, (a, b, c, d), such that a, b, c, d all are special and D(a, b) + D(c, d) < ∞ (i.e there exists a path from city a to city b and another path from city c to city d.)

Your program must read from standard input.

The first line of the input contains 3 integers, N M K denoting the number of cities, the number of roads and the number of special cities respectively.

M lines will follow. Each consisting of 3 integers u_i v_i w_i, meaning that there is a road between city u_i and city v_i which takes w_i seconds to travel in either direction.

The next line contains K distinct integers A₁, A₂, . . . , A_k denoting the list of special cities.

Your program must print to standard output.

The output should contain a single integer on a single line, the optimal minimum value of D(start₁, finish₁) + D(start₂, finish₂) (in seconds).

• 4 ≤ K ≤ N ≤ 10⁵
• 2 ≤ M ≤ min(N(N−1)/2 ,3 × 10⁶)
• 1 ≤ w_i ≤ 1000 for all 1 ≤ i ≤ M
• 1 ≤ u_i ≠ v_i ≤ N for all 1 ≤ i ≤ M