#2368. 「BalticOI 2008」黑手党

内存限制:32 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

题目译自 BalticOI 2008 Day0「Mafia

Byteland 国警方收到了一条匿名举报,其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。
高速公路网包含双向的高速公路段,每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知,黑帮会距港口边最近的收费站进入高速公路,从距仓库最近的收费站离开(不会在出高速后重新进入)。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时,它就会被警察抓住。
从这个角度看,最简单的办法就是在每个收费站处都安排特警班。然而,控制一个收费站需要特定的费用,每个收费站费用不同。警方想要让花费最小,所以他们需要制定一个收费站的最小控制集,这个集合满足两个条件:

  • 所有从港口到仓库的交通必须至少经过集合中的一个收费站
  • 监控这些收费站的费用(即监控每一个收费站费用之和)最小

你可以假设使用高速公路可以从港口到仓库。

任务

写一个程序能够:

  • 从标准输入中读取高速公路网,监控代价和运输的起点和终点
  • 找到收费站的最小控制集
  • 输出这个集合到标准输出

输入格式

标准输入的第一行包含两个整数 n m ,表示收费站的总数和公路段的总数。收费站按 1 n 标号;
第二行包含两个整数 a b ,分别表示距港口和仓库最近的两个收费站编号;
接下来 n 行表示控制费用,第 i 行包含一个整数,表示第 i 个收费站的控制费用 c
接下来 m 行表示高速公路网,第 j 行包含两个整数 x y ,表示在 x y 收费站之间有一条公路段相连。每一条高速公路段只出现一次。

输出格式

唯一的一行输出应包含最小控制集中收费站的编号,以递增顺序输出,用一个空格分隔。
如果有多于一个最小控制集,你的程序可以输出任意一个。

样例

样例输入

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

样例输出

1 4

样例解释

example.gif

p.png

这张图片显示了高速公路网中收费站的编号(在左上角)和控制费用。 1 号和 4 号收费站组成了最小控制集,总控制费用为 5

数据范围与提示

对于 40\% 的测试数据, n\le 20
对于全部数据, 1\le n\le 200,1\le m \le 2\times 10^4 1\le a,b\le n,a\not =b 1\le c\le 10^7 1\le x<y\le n