1210번 - 마피아 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1953 | 577 | 420 | 26.820% |
문제
2015년 구단에서 방출된 셰브첸코는 한때 그의 팬이었던 구단주 로만 아브라히모비치의 도움으로 러시아의 경찰이 되었다.
어느 날 그는 그가 감시를 하고 있는 마피아 조직에서 대규모 이동이 있음을 감지했다. 마피아는 고속도로를 통해서 이동을 하는데 고속도로망은 n개의 톨게이트와 그 사이를 있는 m개의 고속도로로 이루어져있다. 고속도로의 중간에서 밖으로 나가거나 중간으로 들어오지는 못한다고 하자. 즉 모든 이동은 톨게이트와 고속도로를 거쳐서 이루어져야 된다는 것이다. 마피아의 시작점과 도착점이 주어질 때 우리는 몇 개의 톨게이트를 점거해서 마피아가 시작점에서 도착점까지 우리의 점거된 톨게이트를 지나지 않고서는 도착할 수 없게 하고 싶다. 그런데 톨게이트를 점거하는데에는 각각의 톨게이트마다 고유한 비용이 든다.
이때 점거비를 최소화 하며 마피아의 움직임을 막기 위해 점거해야되는 도시들을 출력하여라.
입력
첫 줄에는 톨게이트의 개수 n과 고속도로의 개수 m이 주어진다.(1 ≤ n ≤ 200, 1 ≤ m ≤ 20000) 톨게이트의 번호는 1부터 n까지로 주어진다고 할 때, 다음 줄에는 마피아의 시작점과 도착점이 주어진다. 그리고 그 다음 n개의 줄에는 각 톨게이트별 점거비용이 나온다. 그 뒤 m개의 줄에는 톨게이트를 연결하는 고속도로들이 주어진다. 점거비용은 10,000,000보다 작거나 같은 자연수이다.
출력
점거비를 최소화 하며 마피아의 움직임을 막기 위해 점거해야되는 도시들을 오름차순으로 출력하여라.
예제 입력 1
5 6 5 3 2 4 8 3 10 1 5 1 2 2 4 4 5 2 3 3 4
예제 출력 1
1 4
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호