시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 381 81 52 18.505%

문제

2015년 구단에서 방출된 셰브첸코는 한때 그의 팬이었던 구단주 로만 아브라히모비치의 도움으로 러시아의 경찰이 되었다.

어느날 그는 그가 감시를 하고 있는 마피아 조직에서 대규모 이동이 있음을 감지했다. 마피아는 고속도로를 통해서 이동을 하는데 고속도로망은 n개의 톨게이트와 그 사이를 있는 m개의 고속도로로 이루어져있다. 고속도로의 중간에서 밖으로 나가거나 중간으로 들어오지는 못한다고 하자. 즉 모든 이동은 톨게이트와 고속도로를 거쳐서 이루어져야 된다는 것이다. 마피아의 시작점과 도착점이 주어질 때 우리는 몇 개의 톨게이트를 점거해서 마피아가 시작점에서 도착점까지 우리의 점거된 톨게이트를 지나지 않고서는 도착할 수 없게 하고 싶다. 그런데 톨게이트를 점거하는데에는 각각의 톨게이트마다 고유한 비용이 든다.

이때 점거비를 최소화 하며 마피아의 움직임을 막기 위해 점거해야되는 도시들을 출력하여라.

입력

첫 줄에는 톨게이트의 개수 n과 고속도로의 개수 m이 주어진다.(1<=n<=200, 1<=m<=20000) 톨게이트의 번호는 1부터 n까지로 주어진다고 할 때, 다음 줄에는 마피아의 시작점과 도착점이 주어진다. 그리고 그 다음 n개의 줄에는 각 톨게이트별 점거비용이 나온다. 그 뒤 m개의 줄에는 톨게이트를 잇는 고속도로들이 주어진다.

출력

점거비를 최소화 하며 마피아의 움직임을 막기 위해 점거해야되는 도시들을 오름차순으로 출력하여라.

예제 입력

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

예제 출력

1 4

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 6번

  • 문제를 번역한 사람: author4
  • 빠진 조건을 찾은 사람: HyehwA