시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 58 17 15 32.609%

문제

드래곤 나라에는 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 ⩽ 10^5, 0 ⩽ Ni ⩽ 10^5)이 주어진다. 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

힌트

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2014 G번