問題一覧 > 通常問題

No.2604 Initial Motion

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 70
作問者 : 👑 amentorimaru / テスター : 👑 seekworser 👑 獅子座じゃない人
お気に入りにしたユーザー ProblemId : 10321 / 自分の提出
問題文最終更新日: 2024-01-11 12:53:01
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 414 (順位表) の他の問題:

Problem Statement

In a certain virtual space, there is a game in which players pick up weapons found on the map and fight.


$K$ users are going to play this game. The map of this game is a connected simple undirected graph with $N$ vertices and $M$ edges. Edge $i$ connects vertices $U_i$ and $V_i$ bidirectionally, and the distance between them is $D_i$.

At the start of the game, user $i$ is at vertex $A_i$. Also, $B_i$ weapons lie on vertex $i$. Each user can pick up at most one of the weapons lying around, but cannot pick up a weapon that someone has already picked up.

At the start, no user has a weapon, so everyone begins by moving between vertices and picking up weapons. (If a weapon is available without moving, the user can pick it up right there.)

It is guaranteed that the total number of weapons is at least $K$. Find the minimum possible value of the total distance moved by all users until every user has picked up a weapon.

Input

$K\ N\ M$
$A_1\ A_2\ \dots A_K$ 
$B_1\ B_2\ \dots B_N$ 
$U_1\ V_1\ D_1$
$U_2\ V_2\ D_2$
$\vdots$
$U_M\ V_M\ D_M$

  • All inputs are integers.
  • $ 1\le K \le 2000$
  • $ 1\le N \le 2000$
  • $ N-1\le M \le \min \left( \frac{N(N-1)}{2},2000 \right) $
  • $ 1\le A_i \le N$
  • $ 0\le B_i \le K$
  • $ K \le \sum B_i$
  • $1\le U_i,V_i \le N$
  • $ U_i \neq V_i$
  • $1\le D_i \le 10^{12}$
  • The given graph is simple and connected.

Output

Output the answer.

Sample

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

For example, user $1$ starts at vertex $1$ and can pick up a weapon without moving, at distance $0$.

User $2$ starts at vertex $1$, moves to vertex $2$, and can pick up a weapon at distance $4$.

User $3$ starts at vertex $1$, moves to vertex $3$, and can pick up a weapon at distance $5$.

User $4$ starts at vertex $4$, moves to vertex $5$ and then to vertex $3$, and can pick up the second weapon at distance $4$.

In this case, the total distance moved by all users is $0+4+5+4=13$.

It is impossible for everyone to pick up a weapon with a smaller total distance, so output $13$.

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

Everyone heads to vertex $1$ at once.

Sample 3
Input
20 10 10
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
4 0 0 3 3 0 1 5 0 4
1 2 4
2 3 2
3 4 3
4 5 1
5 6 2
6 7 4
7 8 5
2 9 3
6 9 1
9 10 8
Output
54

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