10319번 - 좀비 아포칼립스 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 725 | 340 | 190 | 37.849% |
문제
때는 2020년, 당신과 그 일행은 좀비로 황폐화된 대도시의 어느 마을 안에 갇혔다. 당신들 또한 바이러스에 감염되었기 때문에 좀비가 되기 전에 빨리 병원을 찾아 치료해야 한다. 당신들은 과학자이기에 멍청하게 좀비들에게 돌격해 길을 뚫기보다는 좀비들 몰래 슬금슬금 이동하는 게 안전하다. 하지만 도처에 널린 것이 좀비라 몇몇 도로는 다른 곳보다 슬금슬금 지나가는 데 시간이 많이 걸린다. 때로는 다같이 다니는 것보다 여러 무리로 떨어져서 각자 나아가는 게 훨씬 안전할 것이다.
게다가, 이 좀비들은 크게 감염되지는 않아서 머리 뒤편에 눈이 달려있거나 하지는 않다. 따라서 몇몇 도로는 한쪽 방향으로 이동하는 건 쉽지만, 역행하는 것은 어렵거나 불가능할지도 모른다.
당신들 일행 중 최대 몇 명이 좀비가 되기 전에 좀비들을 피해서 병원에 도달할 수 있을까?
입력
첫째 줄에 테스트 케이스의 개수가 주어지며, 각 테스트 케이스는 다음과 같이 이루어져 있다. 주어지는 모든 값은 정수이다.
- 첫째 줄에 장소의 개수 n이 주어진다. (1 ≤ n ≤ 1 000)
- 다음 줄에 일행이 처음에 있던 장소 i, 일행의 사람 수 g, 좀비에 감염되기까지 걸리는 시간 s가 주어진다. (1 ≤ i ≤ n, 1 ≤ g ≤ 100, 1 ≤ s ≤ 100)
- s초에 병원에 도착한 경우 좀비가 되기 전에 병원을 찾은 것이다.
- 다음 줄에 병원의 수 m이 주어진다. (1 ≤ m ≤ n)
- 이어서 m개의 줄에 각 병원이 위치한 장소 번호가 주어진다. (1 ≤ x ≤ n)
- 다음 줄에 도로의 개수 r이 주어진다. (0 ≤ r ≤ 1 000)
- 이어서 r개의 줄에 각 도로의 정보를 나타내는 값 a, b, p, t가 주어진다. (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ p ≤ 100, 1 ≤ t ≤ 100) 이 도로는 a에서 b로 가는 도로이며, 매 단위시간마다 p명이 도로에 들어설 수 있으며 지나가려면 단위시간 t가 소요된다는 뜻이다.
어떤 장소 쌍에 대해 도로는 최대 2개(한 방향당 1개)까지 존재한다. 각 장소는 충분히 안전하여 얼마든지 가만히 서서 기다려도 안전하다. 또한 한 장소에 있을 수 있는 사람 수에도 제한이 없다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 감염되지 않고 병원에 도달하는 최대 사람 수를 출력한다.
예제 입력 1
2 4 3 8 5 2 2 4 5 1 2 1 3 3 2 1 4 3 1 2 1 1 4 1 3 3 4 1 3 4 3 10 5 2 2 4 5 1 2 1 3 3 2 1 4 3 1 2 1 1 4 1 3 3 4 1 3
예제 출력 1
8 9
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2014 A번
- 문제를 번역한 사람: kks227
- 빠진 조건을 찾은 사람: man_of_learning
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호