笨笨的洪水堵截
测试数据来自 system/1590
背景
笨笨:汗……
路人甲:大汗……
笨笨:瀑布汗……
路人甲:大瀑布汗……
笨笨:懒得和你汗……
路人甲:怎么这么多水的啊?
描述
一场洪水即将到来,笨笨要想方设法堵截它!
堵截洪水的唯一办法是在洪水经过河流的岔道口放上石头!(笨笨在将小石头一颗一颗地垒好……囧)
对于不同的岔道口,需要的石头量不同,而笨笨所要消耗的体力也不同。
为了不太累,笨笨决定要用最少的体力来堵截这场洪水,洪水从岔道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。
来源
笨笨原创。