文理学院程序设计在线练习


军事输送

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 5   Accepted Submission(s): 1
Problem Description

战场上有n个位置,有m条双向路径连接其中的一些位置。
在灼热的战场上,军事物资的输送是无可避免的。
现在你作为战场的军需官,需要尽快调度战场上的某种物资。
每个位置对于该物资的需求情况是ai,如果大于0则说明该位置富余该物资,可以调度给其他位置ai个单位资源。如果小于0则说明该位置极度缺乏该物资,需要其他地方输送至少ai个单位资源。
每个单位物资的运输代价为它的运输距离,现在你作为军需官,请告知使所有紧缺物资的地区得到足够的资源的最小运输代价和。
如果无法满足要求,则输出-1。

Input

第一行输入一个整数T表示数据组数(T<=21)。
每组数据第一行输入两个整数n,m,分别代表位置数量和路径数量。
随后一行输入n个整数,表示第i个位置对于该物资的需求量为ai
随后m行,每行输入三个整数u,v,w,表示u和v之间有一条距离为w的双向路径。其中,
1 <= n,m,u,v <= 500
1 <= w <= 1000
-1000 <= ai <= 1000

Output

对于每组数据输出一行,包含一个整数,表示使所有紧缺物资的地区得到足够的资源的最小运输代价和;如果无法满足要求,则输出-1。

Sample Input
2
3 3
10 0 -5
1 2 1
2 3 3
1 3 5
2 1
5 -7
1 2 100
Sample Output
20
-1
Hint

样例1中,位置1要运送给位置3五个单位的资源,此时位置1到位置3通过1->2->3距离为4,故总代价为20。
样例2中,位置1无法满足位置2七个单位的要求,故无法达成,输出-1。

Source

2019校赛