No.2604 Initial Motion
タグ : / 解いたユーザー数 70
作問者 : 👑
amentorimaru
/ テスター :
👑 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もしくは右上の雲マークをクリックしてアカウントを作成してください。