시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 373 | 108 | 85 | 28.912% |
드래곤 나라에는 N개의 도시와 M개의 도로가 있다. 도시들은 1번 부터 N번까지 번호가 붙어 있으며 각 도로는 두개의 도시를 연결한다. 이 N개의 도시에는 전체 합이 K마리인 D1, D2, ... DK드래곤이 살고 있다. 도시 Ci에 살고 있는 드래곤 Di는 처음에 Si의 머리를 가지고 있다. 드래곤이 살아있는 동안 매 분 Ni개의 새로운 머리가 자란다. 드래곤은 하나 이상의 머리가 남아 있으면 생존할 수 있다.
우린 드래곤을 처치하기 위해 워리어를 고용할것이다. 매 분마다 각 워리어는 인접한 도시로 이동하거나 자신이 머물고 있는 도시의 드래곤의 머리 하나를 자를 수 있다. 우리는 워리어가 매 분마다 취할 전략을 정할 수 있다. 또한 우리는 각 워리어가 머무는 최초 도시를 지정할 수 있다.
유한한 시간에 모든 드래곤을 죽이기 위해 필요한 최소 워리어 수를 구하라.
여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세개의 정수 N, M, K (1 ≤ N ≤ 300, 0 ≤ M ≤ N(N-1), 1 ≤ K ≤ 1000)가 주어진다. 그 후 M개의 줄이 주어진다. 각 줄에는 도시 a와 b 사이의 연결을 가리키는 두개의 정수 a, b (1 ≤ a ≠ b ≤ N)가 주어진다. 이후 K개의 줄이 주어진다. K개 줄의 i번째 줄에는 드래곤 Di에 대한 값 Ci, Si, Ni (1 ≤ Ci ≤ N, 1 ≤ Si ≤ 105, 0 ≤ Ni ≤ 105)이 주어진다. 0 0 0이 입력되면 테스트 케이스는 종료된다.
각 테스트 케이스에 대해 결과는 모든 드래곤을 죽일 수 잇는 최소 워리어 수를 출력해야한다.
2 1 1 1 2 1 7 4 4 4 2 1 2 2 4 4 1 1 3 1 2 3 2 3 1 0 0 0
5 2
ICPC > Regionals > Asia West Continent > Iran > Tehran Site 2014 G번