問題一覧 > 通常問題

No.1814 Uribo Road (Easy)

レベル : / AI推定難易度 : 1125 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : MasKoaTS / テスター : Shirotsume
お気に入りにしたユーザー ProblemId : 7106 / 自分の提出
問題文最終更新日: 2024-12-01 12:42:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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もしくは右上の雲マークをクリックしてアカウントを作成してください。