No.1814 Uribo Road (Easy)
タグ : / 解いたユーザー数 36
作問者 :
MasKoaTS
/ テスター :
Notes
This problem has the same problem statement as the problem Uribo Road, but different constraints and execution time limit.
Note that the execution time limit of this problem is somewhat strict, so even the intended solution may get TLE in some languages or implementations.
In particular, if you solve this problem in Python, we recommend choosing PyPy3 as the implementation.
Problem Statement
Mt. Hakkou has $N$ points numbered $1, 2, \cdots, N$,
and these points are connected by $M$ bidirectional roads numbered $1, 2, \cdots, M$.
Road $i$ $(1 \leq i \leq M)$ connects point $A_{i}$ and point $B_{i}$, and the distance between them is $C_{i}$.
Koa commutes from her home at point $1$ on this mountain to Koume Academy at point $N$,
and on the way, it is her daily routine to pet all the wild boars living on the $K$ roads $R_{1},R_{2},\cdots,R_{K}$.
Suppose Koa decides her route from her home to Koume Academy so that it passes through every one of the roads $R_{1},R_{2},\cdots,R_{K}$ at least $1$ time,
and the total distance of the entire route is minimized. Find that travel distance.
Note that she may pass through the same road $2$ or more times, and may visit point $N$ $2$ or more times.
Constraints
The parts that differ from the problem Uribo Road are shown in red.
$2 \leq N \leq \boldsymbol{ \textcolor {red} {200} }$
$\displaystyle N-1 \leq M \leq \boldsymbol{ \textcolor {red} {\frac{N \times (N-1) }{2} } }$
$1 \leq K \leq \min ( \boldsymbol{ \textcolor {red} {5} }, M)$
$1 \leq R_{i} \leq M$ $(1 \leq i \leq K)$
$R_{i} \neq R_{j}$ $(1 \leq i < j \leq K)$
$1 \leq A_{i},B_{i} \leq N$ and $A_{i} \neq B_{i}$ $(1 \leq i \leq M)$
$(A_{i},B_{i}) \neq (A_{j},B_{j})$ and $(A_{i},B_{i}) \neq (B_{j},A_{j})$ $(1 \leq i < j \leq M)$
$1 \leq C_{i} \leq 10^{4}$ $(1 \leq i \leq M)$
Any $2$ points can be reached from each other by traveling along $1$ or more roads
All inputs are integers
Input
The input is given in the following format.
$N$ $M$ $K$
$R_{1}$ $R_{2}$ $\cdots$ $R_{K}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
$\vdots$
$A_{M}$ $B_{M}$ $C_{M}$
Line $1$ contains $N$, $M$, and $K$ in this order, separated by single-byte spaces
Line $2$ contains $R_{1},R_{2},\cdots,R_{K}$ in this order, separated by single-byte spaces
Line $(2+i)$ $(1 \leq i \leq M)$ contains $A_{i}$, $B_{i}$, and $C_{i}$ in this order, separated by single-byte spaces
Output
Output the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
5 6 2 3 4 1 2 3 1 3 1 2 3 10 3 4 20 3 5 5 4 5 7
Output
40
By moving through points in the order $1 \to 2 \to 3 \to 4 \to 5$, she can pass through both road $3$, which connects point $2$ and point $3$, and road $4$, which connects point $3$ and point
$4$,
and in that case the travel distance to point $5$ is minimized.
Sample 2
Input
6 5 5 2 4 3 5 1 1 2 2 3 2 4 2 4 6 5 4 8 4 6 10
Output
42
She should move through points in the order $1 \to 2 \to 3 \to 2 \to 4 \to 5 \to 4 \to 6$.
She may pass through the same road $2$ or more times.
Sample 3
Input
4 6 3 2 3 4 1 2 4 1 3 6 1 4 1 2 3 3 2 4 2 3 4 1
Output
13
She should move through points in the order $1 \to 3 \to 2 \to 4 \to 1 \to 4$.
She may visit the final point $2$ or more times.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。