P10339 [THUSC 2019] Supply Plan.

Country T is a small country. Due to a once-in-a-century cold wave, some cities have been severely affected. The government of Country T plans to send rescue teams from the capital to help the affected cities, and at the same time build several supply points to support the rescue teams.

Country T has a total of $N$ cities (numbered from $1$ to $N$). These cities are connected by $M$ undirected roads, and each road has its own length (all greater than $0$). There are $K$ affected cities. The government of Country T plans to send one rescue team from the capital (City $1$) to each of these $K$ cities. To better complete the rescue operations, the government also plans to build supply points in some cities. However, due to factors such as geography and funding, not every city can build a supply point (whether a city can build a supply point is unrelated to whether it is the capital or an affected city). To finish the rescue as soon as possible, each of the $K$ rescue teams will travel to its destination only along shortest paths. The government wants to build as few supply points as possible among the cities where supply points can be built, so that for every rescue team, at least one shortest path to its destination passes through at least one supply point. You are given the information of the cities and roads in Country T. You need to compute the minimum number of supply points the government must build.

The first line contains three integers $N, M, K$, with meanings as described above. It is guaranteed that $1 \le N \le 200$, $0 \le M \le 10000$, and $1 \le K \le 20$. The second line contains $N$ integers, each being $0$ or $1$, indicating in order whether the corresponding city can build a supply point ($1$ means it can). The third line contains $K$ positive integers $x_i$, representing the indices of the affected cities. It is guaranteed that these $K$ numbers are all distinct and the capital is not affected, and $1 \le x_i \le N$. The next $M$ lines each contain three integers $u, v, w$, indicating that there is a road of length $w$ between City $u$ and City $v$, where $1 \le u, v \le N$ and $0 < w \le 10^9$. The input guarantees that there exists at least one solution that satisfies the requirements in the statement.

Output one integer, the answer.

**Sample Explanation 1** The graph corresponding to this sample is shown below, where node $1$ is the capital and nodes $3, 4, 6$ are affected cities:  For this sample, at least $2$ supply points are needed. They can be built at $2, 5$ or at $2, 6$. Note that they cannot be built at nodes $3, 5$, because the only shortest path from the capital to node $4$ is $1 \rightarrow 2 \rightarrow 4$, and there is no shortest path that passes through nodes $3, 5$. **Subtasks** | Test Point | $N$ | $M$ | $K$ | Special Property | | :--: | :--: | :--: | :--: | :--: | | $1\cdots 2$ | $1 \le N \le 200$ | $M = N - 1$ | $1 \le K \le 20$ | The input is a tree. | | $3\cdots 6$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 4$ | None. | | $7\cdots 12$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 16$ | None. | | $13\cdots 20$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 20$ | None. | Translated by ChatGPT 5