F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1339. -- [Baltic2008]Mafia

1339: [Baltic2008]Mafia

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 511  Solved: 329
[Submit][Status][Discuss]

Description

匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控. 对于每个车站进行布控都需要一定的代价,
现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后,匪徒无法从原定的初始点到达目标点

Input

第一行输入N,M代表车站的总个数,及有多少条双向边连接它们
第二行给出两个数a,b,代表匪徒的出发点及目标点.1<=a,b<=N,a<>b. 
再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000 
再下来M行,用于描述图的结构.
2<=n<=200 , 1 <=m<=20000

Output

最少需要多少Money

Sample Input

5 6
5 3
2
4
8
3
10
1 5
1 2
2 4
4 5
2 3
3 4

Sample Output

5

HINT

Source

[Submit][Status][Discuss]

HOME Back