#1163. [Baltic2008] Mafia

[Baltic2008] Mafia

题目描述

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

输入格式

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

第二行给出两个数 a,ba,b,代表匪徒的出发点及目标点。

再下来有 nn 行,给出对第 ii 个车站进行布控所需要的 Money,再下来 mm 行,用于描述图的结构。

输出格式

最少需要多少 Money。

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

数据范围

对于 100%100\% 的数据,2n2002 \le n \le 2001m2×1041 \le m \le 2\times 10 ^ 41a,bn1\le a,b\le n,Money 不超过 10710^7