A30297.【蓝桥杯】城市建设

普及-

蓝桥杯

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

栋栋居住在一个繁华的C市中,然而,这个城市的道路大都年久失修。市长准备重新修一些路以方便市民,于是找到了栋栋,希望栋栋能帮助他。

C市中有n个比较重要的地点,市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点,每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过,也可以在其中的一些地点建设码头,所有建了码头的地点可以通过河道连接。


栋栋拿到了允许建设的道路的信息,包括每条可以建设的道路的花费,以及哪些地点可以建设码头和建设码头的花费。


市长希望栋栋给出一个方案,使

输入格式

输入的第一行包含两个整数n, m,分别表示C市中重要地点的个数和可以建设的道路条数。所有地点从1到n依次编号。

接下来m行,每行三个整数a, b, c,表示可以建设一条从地点a到地点b的道路,花费为c。若c为正,表示建设是花钱的,如果c为负,则表示建设了道路后还可以赚钱(比如建设收费道路)。


接下来一行,包含n个整数w_1, w_2, …, 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

    9
首页