【Minimum】

【问题描述】

给出一幅由n个点m条边构成的无向带权图。

其中有些点是黑点,另外点是白点。

现在每个白点都要与它距离最近的黑点通过一些边连接(就是最短路)(如果有很多歌,可以选取其中任意一个。),我们想要使得花费的代价最小。请问这个最小代价是多少?

【输入格式】

第一行两个整数n,m;

第二行n个整数,0表示白点,1表示黑点

接下来m行,每行三个整数x y z,表示一条连接x和y点,权值为z的边。

【输出格式】

如果无解,输出impossible;

否则,输出最小代价。

【输入样例】

5 7

0 1 0 1 0

1 2 11

1 3 1

1 5 17

2 3 1

3 5 18

4 5 3

2 4 5

【输出样例】

5

【样例说明】

选2 4 6三条边;

【数据范围】

对30%的输入数据:1≤n ≤10,1≤m≤20;

对100%的输入数据:1≤n≤100000,1≤m≤200000,1≤z≤1000000000

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*