/ Vijos / 题库 /

笨笨的洪水堵截

笨笨的洪水堵截

背景

笨笨:汗……
路人甲:大汗……
笨笨:瀑布汗……
路人甲:大瀑布汗……
笨笨:懒得和你汗……
路人甲:怎么这么多水的啊?

描述

一场洪水即将到来,笨笨要想方设法堵截它!
堵截洪水的唯一办法是在洪水经过河流的岔道口放上石头!(笨笨在将小石头一颗一颗地垒好……囧)
对于不同的岔道口,需要的石头量不同,而笨笨所要消耗的体力也不同。

为了不太累,笨笨决定要用最少的体力来堵截这场洪水,洪水从岔道0出发,笨笨要防止洪水冲到岔道n。

格式

输入格式

输入有多组,输入第一行为组数(组数小于15)。

每组输入格式如下。

第一行两个数n,m(0<n<=50,0<=m<=200)。

第二行n-1个数,第i个数表示堵截该岔道需要消耗笨笨k[i]的体力。(i=1 to n-1,每个k[i]都是正整数)
接下来m行,每行两个数a,b,表示岔道a和岔道b之间有河道连接。

输出格式

对于每一组输入一个输出。

每组输入输出一行,表示笨笨所需要消耗的最小体力。

若洪水不可能冲到岔道n,则输出“Min!”,若洪水无法阻止,则输出“Max!”。

样例1

样例输入1

1
4 5
2 3 4
0 1
0 3
1 2
2 4
3 4

样例输出1

6

限制

1s

提示

对样例的解释:
洪水从0出发。

而笨笨要阻止洪水流到n。

耗体力最少的堵截方式就是将岔道1和岔道3堵上即可。

消耗体力最小总和为2+4=6。

来源

笨笨原创。

信息

ID
1590
难度
8
分类
图结构 | 网络流 点击显示
标签
递交数
1791
已通过
192
通过率
11%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

笨笨工作室2009提高组模拟赛