1839: [Baltic2008]黑手党(Mafia)

给定一个无向图，一个物体从图中A点要运动到B点（A,B之间至少经过一点），现在需要派人拦截该物体。派人到每个点需要不同的费用，请问如何安排保证拦截该物体使得派人的总费用最少。

图中方框左上角的小数字是顶点号，中间大数字是在该点的费用。本题的最小费用是拦信1，4点，总费用是5

第1行：2个空格分开的整数N(2≤ N ≤200)和M(1≤ M ≤20000), N表示顶点数，M表示边数。顶点编号从1～N

第2行：2个空格分开的整数A和B(1≤A,B≤N, A≠B),分别表示起点和终点

接下来N行每行描述在一个顶点的守卫费用，费用是一个不超过10000000的正整数

接下来M行描述图结构。每行2个整数 X 和 Y，表示在顶点X和Y之间有一条边

第1行：一列空格分开的整数，表示花最小的费用拦截物体必须守卫的顶点序列。顶点从小到大输出。

如果有多组解，输出字典序最小的一组解。

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

1 4