#1339. [Baltic2008]Mafia

题目描述

匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控. 对于每个车站进行布控都需要一定的代价,

现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后，匪徒无法从原定的初始点到达目标点

输入格式

第一行输入N,M代表车站的总个数,及有多少条双向边连接它们

第二行给出两个数a,b,代表匪徒的出发点及目标点.1<=a,b<=N,a<>b.

再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000

再下来M行,用于描述图的结构.

2<=n<=200 , 1 <=m<=20000

输出格式

最少需要多少Money

样例

样例输入

5 6  

5 3  

2  

4  

8  

3  

10  

1 5  

1 2  

2 4  

4 5  

2 3  

3 4

样例输出

5

数据范围与提示