AT_maximum_2013_f 3人の騎士と1匹の犬

「为了主人的缘故，无论如何也要完成任务。」他们是侍奉主人的骑士（这里有 3 人和 1 只动物，这只动物被称为狗）。他们为了治愈主人的疾病，打倒强大的魔力持有者，并从魔力持有者那里夺取并收集魔力。他们相信只要收集到足够的魔力就能治愈主人。就在前几天，他们刚刚从两位魔法使那里收集到了魔力。虽然魔力的收集进展顺利，但主人的病情却比预想的要发展得更快。再加上，不能从同一个魔力持有者那里多次夺取魔力，因此还必须考虑寻找收集对象所需的时间。基于这些原因，虽然之前一直是几个人组队行动，但今后只能各自单独行动。为了今后的战斗，体力应当尽量保存，当然，移动也会消耗体力（称为移动力），所以应尽量减少移动。 你的任务是：给定骑士和魔力持有者的位置及魔力量，当每个骑士最多只能收集一位魔力持有者的魔力，并且收集到的魔力量总和最大时，求所需的最小移动力。 移动力与曼哈顿距离成正比。例如，若骑士的坐标为 $(1,1)$，魔力持有者的坐标为 $(2,3)$，则骑士需要 $3$ 的移动力才能到达魔力持有者的位置。此外，保证世界中不会有同名的人物。 输入通过标准输入按以下格式给出。 > $N$ $M$ > $KNIGHT\_NAME_1$ $KX_1$ $KY_1$ > ... > $KNIGHT\_NAME_N$ $KX_N$ $KY_N$ > $MAGE\_NAME_1$ $MAGIC_1$ $MX_1$ $MY_1$ > ... > $MAGE\_NAME_M$ $MAGIC_M$ $MX_M$ $MY_M$ 1. 第 1 行给出整数 $N$、$M$。 - $N$ 表示骑士的数量。 - $M$ 表示魔力持有者的数量。 - 保证 $1 \leq N, M \leq 50$。 2. 第 2 行到第 $N+1$ 行的 $N$ 行，每行依次给出骑士的名字、X 坐标和 Y 坐标，字段之间以半角空格分隔。 - $KNIGHT\_NAME_i$ 表示第 $i$ 个骑士的名字。 - $KX_i$ 表示第 $i$ 个骑士的 X 坐标。 - $KY_i$ 表示第 $i$ 个骑士的 Y 坐标。 - 保证 $KNIGHT\_NAME_i$ 为 1 到 20 个半角英数字字符。 - 保证 $0 \leq KX_i, KY_i \leq 10,000$。 3. 第 $N+2$ 行到第 $N+M+1$ 行的 $M$ 行，每行依次给出魔力持有者的名字、魔力量、X 坐标和 Y 坐标，字段之间以半角空格分隔。 - $MAGE\_NAME_i$ 表示第 $i$ 个魔力持有者的名字。 - $MAGIC_i$ 表示第 $i$ 个魔力持有者的魔力量。 - $MX_i$ 表示第 $i$ 个魔力持有者的 X 坐标。 - $MY_i$ 表示第 $i$ 个魔力持有者的 Y 坐标。 - 保证 $MAGE\_NAME_i$ 为 1 到 20 个半角英数字字符。 - 保证 $0 \leq MAGIC_i \leq 10,000,000$，$0 \leq MX_i, MY_i \leq 10,000$。 请输出所需的最小移动力，输出为一行。输出末尾需换行。 例如： ``` 4 4 Sigunum 3 2 Viita 2 2 Shamall 3 3 Zafiira 2 3 Kame 10 1 1 Tora 10 4 1 Hebi 10 1 4 Niwatori 10 4 4 ``` ``` 8 ```

第一行包含两个整数 $N$ 和 $M$。 接下来 $N$ 行，每行包含一个骑士的名字和其坐标 $KX_i$、$KY_i$。 再接下来 $M$ 行，每行包含一个魔力持有者的名字、魔力量 $MAGIC_i$ 以及其坐标 $MX_i$、$MY_i$。

输出一个整数，表示在收集到最大魔力量的前提下所需的最小移动力。输出末尾需换行。

- 每个骑士最多只能收集一位魔力持有者的魔力。 - 每位魔力持有者最多只能被一名骑士收集一次。 - 曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。 - 需要在收集到最大魔力量的前提下，输出所需的最小移动力。 由 ChatGPT 4.1 翻译