問題一覧 > 通常問題

No.748 The Finances of the Yuki Kingdom

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 153
作問者 : 👑 ikd / テスター : nanae
お気に入りにしたユーザー ProblemId : 2382 / 自分の提出
問題文最終更新日: 2018-10-19 07:08: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
yukicoder contest 202 (順位表) の他の問題:

Problem Statement

The Yuki Kingdom has $N$ towns and $M$ roads.
Two towns connected by a road can be traveled between in both directions.
There are never $2$ or more roads connecting the same $2$ towns, and no road has the same town at both ends.
From any town, you can reach any other town by following some roads.

In the Yuki Kingdom, a maintenance cost is incurred for each road every year.
So you, the king, are considering closing some of the roads.
Closed roads can no longer be used to travel between towns, but the maintenance cost is reduced by the amount that was being spent on those roads.
However, to prevent backlash from the citizens, closing roads must not make any town unreachable from any other town.
In other words, even after the roads are closed, it must be possible to travel from any town to any other town by following only some roads that are not closed.

Furthermore, the citizens of the Yuki Kingdom have designated $K$ roads and demand that these roads not be closed, because they are attached to them.

You want to reduce the road maintenance cost as much as possible while accepting the citizens' demands.
What is the maximum total maintenance cost that can be reduced?

Input

$N$ $M$ $K$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$.$
$.$
$a_M$ $b_M$ $c_M$
$e_1$
$e_2$
$.$
$.$
$e_K$

The $1$st line contains the number of towns $N$, the number of roads $M$, and the number of roads $K$ designated by the citizens of the Yuki Kingdom, separated by spaces.

The following $M$ lines, starting from line $2$, give the information about the roads.
The $i$-th of these lines contains the $2$ towns $a_i$ and $b_i$ connected by road $i$ and the maintenance cost $c_i$ of road $i$, separated by spaces.

The following $K$ lines, starting from line $2+M$, give the information about the roads designated by the citizens of the Yuki Kingdom.
The $i$-th of these lines contains an integer $e_i$. This means that the citizens of the Yuki Kingdom demand that road $e_i$ not be closed.

Constraints

  • $1 \le N \le 10^5$
  • $N-1 \le M \le \min(N\times(N-1)/2, 10^5)$
  • $0 \le K \le M$
  • $1 \le a_i < b_i \le N\ (i=1, 2, \dots, M)$
  • If $i \neq j$, then $(a_i, b_i) \neq (a_j, b_j)$
  • From any town, you can reach any other town by following some roads
  • $ 1 \le c_i \le 10^9\ (i=1, 2, \dots, M)$
  • $1 \le e_1 < e_2 < \dots < e_K \le M$
  • All inputs are integers

Output

Output the maximum total maintenance cost that can be reduced. Print a newline at the end.

Sample

Sample 1
Input
5 6 3
1 2 8
1 3 5
2 3 7
2 4 4
3 5 4
4 5 7
1
2
3
Output
7

Roads $1, 2, 3$ cannot be closed because of the citizens' demands.
If $2$ or more of roads $4, 5, 6$ are closed, town $4$ or town $5$ becomes isolated.

In this case, it is optimal to close road $6$. Since the maintenance cost of road $6$ is $7$, output $7$ as the maximum total maintenance cost that can be reduced.

Sample 2
Input
4 5 0
1 2 5
1 3 3
1 4 1
2 3 2
2 4 3
Output
8

Note that $K=0$ is possible.

By closing road $1$ and either road $2$ or road $5$, the maintenance cost can be reduced by a total of $5+3=8$.
This is the maximum total maintenance cost that can be reduced, so output $8$.

Sample 3
Input
6 11 6
4 5 15
2 5 14
2 6 10
1 6 15
3 6 11
2 3 18
5 6 12
1 4 4
2 4 6
1 2 17
3 5 6
1
3
6
7
10
11
Output
50

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。