← 返回题目

题库练习【蓝桥杯】城市建设

← 上一题下一题 →

A3778 | $【蓝桥杯】城市建设$

来源蓝桥杯

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。 C市中有 $n$ 个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。 栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。 市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。

输入格式

输入的第一行包含两个整数 $n, m$，分别表示 $C$ 市中重要地点的个数和可以建设的道路条数。所有地点从$1$ 到 $n$ 依次编号。 接下来m行，每行三个整数 $a, b, c$ ，表示可以建设一条从地点 $a$ 到地点 $b$ 的道路，花费为 $c$ 。若 $c$ 为正，表示建设是花钱的，如果 $c$ 为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。 接下来一行，包含n个整数 $w_1, w_2, \dots, w_n$ 。如果 $w_i$ 为正数，则表示在地点i建设码头的花费，如果 $w_i$ 为 $-1$，则表示地点i无法建设码头。 输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。

输出格式

输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。

输入输出样例

输入 #1

5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1

输出 #1

C++ 编辑器

输入

输出