保卫萝卜

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

《保卫萝卜》是一款超萌的塔防小游戏,玩家在游戏中可以修建各种防御塔保卫萝卜战怪兽,游戏的目的就是防止怪兽吃掉我们的萝卜。 为了收集游戏中的金萝卜奖杯,我们的任务是“保卫一个完整的萝卜”。保卫成功一个萝卜,也就是说没有怪物碰到过这个萝卜,这就需要用金币修防御塔来消灭在地图中从刷怪点冲向萝卜的怪物。如果给出游戏的地图,请问:至少需要多少花多少金币才能确保完成任务?

Input

题目包含多组输入数据,对于每一组输入数据 : 第一行两个整数N,M(<500)。N表示地图上的顶点数,M表示边数。 第二行包含N个int 类型的整数,A1 ~An。若Ai =0,表示第i个顶点是萝卜;若Ai<0,表示第i个顶点是刷怪点;若Ai>0,表示不依靠别的防御消灭最强的一波经过第i个顶点的怪物需要花费Ai个金币。 之后的M行各有两个整数,u,v(<500)表示第u个顶点到第v个顶点之间有一条怪物可以任意通行的边。

Output

对于每组输入数据: 如果能完成任务,输出至少需要花多少金币才能确保我们能保卫一个萝卜;如果不能完成任务,输出“Poor Carrot”。

Sample Input

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

Sample Output

Case 1: 2
Case 2: Poor Carrot
Case 3: 2

Hint

萝卜所在的点是无法进行防御的,所以不要在有萝卜的地方浪费金币啦。

Source

“掌赢杯”南京理工大学第六届程序设计大赛网络预选赛

提交代码