P6192 [Template] Minimum Steiner Tree

You are given an undirected connected graph $G=(V,E)$ with $n$ vertices and $m$ weighted edges. You are also given a set $S$ containing $k$ vertices. Choose a subgraph $G'=(V',E')$ of $G$ such that: 1. $S\subseteq V'$. 2. $G'$ is connected. 3. The sum of edge weights in $E'$ is minimized. You only need to output the sum of edge weights in $E'$.

The first line contains three integers $n,m,k$, representing the number of vertices, the number of edges in $G$, and the size of $S$. The next $m$ lines each contain three integers $u,v,w$, indicating an undirected edge between vertices $u$ and $v$ with weight $w$. The next line contains $k$ distinct positive integers, representing the elements of $S$.

The first line contains one integer, the minimum possible sum of edge weights in $E'$.

[Sample Explanation] The graph in the sample is shown in the figure below. The red vertices are the elements in $S$, and the red edges are the elements in $E'$. In this case, the sum of all edge weights in $E'$ is $2+2+3+4=11$, which is the minimum.  --- [Constraints] For $100\%$ of the testdata, $1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6$. The given undirected graph is guaranteed to be connected, but there **may** be multiple edges and self-loops. Translated by ChatGPT 5