P5304 [GXOI/GZOI2019] Traveler

Country J has $n$ cities, connected by $m$ one-way roads. The length of each road is known. One day, Rainbow, who lives in Country J, invites Vani to visit. However, as an experienced traveler, Vani is only interested in $k$ cities in Country J that have a long history and unique natural scenery. To improve the travel experience, Vani wants to know the minimum value among the “pairwise shortest paths” between the cities he is interested in (that is, among all pairs of cities he is interested in, the shortest-path distance of the closest pair). You may have already guessed the story — Vani will be busy traveling elsewhere these days, so please help him solve this problem.

Each test point contains multiple test cases. The first line is an integer $T$, the number of test cases. Note that the test cases are independent of each other. For each test case, the first line contains three positive integers $n, m, k$, representing $n$ cities in Country J (numbered from $1 \sim n$), $m$ roads, and the number $k$ of cities that Vani is interested in. The next $m$ lines each contain $3$ positive integers $x, y, z$, indicating that there is a one-way road from city $x$ to city $y$ with length $z$. Note that $x$ and $y$ may be equal, and the same pair $(x, y)$ may appear multiple times. The next line contains $k$ positive integers, the indices of the cities that Vani is interested in.

The output should contain $T$ lines. For each test case, output one integer: the minimum value among the pairwise shortest-path distances between the $k$ cities.

### Sample Explanation For the first test case, the shortest path from $1$ to $3$ is $5$; from $1$ to $6$ is $7$; $3$ and $6$ cannot reach each other. So the closest pair is $1, 3$, and the minimum distance is $5$. For the second test case, the shortest path from $1$ to $2$ is $6$; from $5$ to $3$ is $6$; all other pairs of points cannot reach each other. So the closest pairs are $1, 2$ and $5, 3$, and the minimum distance is $6$. ### Constraints $2 \le k \le n$, $1 \le x, y \le n$, $1 \le z \le 2 \times 10^9$, $T \leq 5$. |Test Point ID|Scale of $n$|Scale of $m$|Notes| |:-:|:-:|:-:|:-:| |$1$|$\le 1,000$|$\le 5,000$|None| |$2$|$\le 1,000$|$\le 5,000$|None| |$3$|$\le 100,000$|$\le 500,000$|The graph is guaranteed to be a directed acyclic graph| |$4$|$\le 100,000$|$\le 500,000$|The graph is guaranteed to be a directed acyclic graph| |$5$|$\le 100,000$|$\le 500,000$|The graph is guaranteed to be a directed acyclic graph| |$6$|$\le 100,000$|$\le 500,000$|None| |$7$|$\le 100,000$|$\le 500,000$|None| |$8$|$\le 100,000$|$\le 500,000$|None| |$9$|$\le 100,000$|$\le 500,000$|None| |$10$|$\le 100,000$|$\le 500,000$|None| Admin note on 2024-12-18: [There may be self-loops in test point 5](https://www.luogu.com.cn/discuss/1022672)。 Translated by ChatGPT 5