시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 95 27 22 29.333%

문제

드래곤 나라에는 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이 입력되면 테스트 케이스는 종료된다.

출력

각 테스트 케이스에 대해 결과는 모든 드래곤을 죽일 수 잇는 최소 워리어 수를 출력해야한다.

예제 입력 1

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

예제 출력 1

5
2
W3sicHJvYmxlbV9pZCI6IjEwNjA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNGRjXHViNzk4XHVhY2U0IFx1YzhmZFx1Yzc3NFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViNGRjXHViNzk4XHVhY2U0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0MCAxXHViYzg4IFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVkNTY5XHVjNzc0IEtcdWI5YzhcdWI5YWNcdWM3NzggRDEsIEQyLCAuLi4gREtcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjMmRjIENpXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViNGRjXHViNzk4XHVhY2U0IERpXHViMjk0IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBTaVx1Yzc1OCBcdWJhMzhcdWI5YWNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNGRjXHViNzk4XHVhY2U0XHVjNzc0IFx1YzBiNFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWIzZDlcdWM1NDggXHViOWU0IFx1YmQ4NCBOaVx1YWMxY1x1Yzc1OCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYTM4XHViOWFjXHVhYzAwIFx1Yzc5MFx1Yjc4MFx1YjJlNC4gXHViNGRjXHViNzk4XHVhY2U0XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViYTM4XHViOWFjXHVhYzAwIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjMGRkXHVjODc0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjliMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjYzk4XHVjZTU4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM2Y2NcdWI5YWNcdWM1YjRcdWI5N2MgXHVhY2UwXHVjNmE5XHVkNTYwXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI5ZTQgXHViZDg0XHViOWM4XHViMmU0IFx1YWMwMSBcdWM2Y2NcdWI5YWNcdWM1YjRcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YjNjNFx1YzJkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjNzBcdWIwOTggXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmEzOFx1YmIzY1x1YWNlMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjRkY1x1Yjc5OFx1YWNlNFx1Yzc1OCBcdWJhMzhcdWI5YWMgXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNmNjXHViOWFjXHVjNWI0XHVhYzAwIFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHVjZGU4XHVkNTYwIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWFjMDEgXHVjNmNjXHViOWFjXHVjNWI0XHVhYzAwIFx1YmEzOFx1YmIzNFx1YjI5NCBcdWNkNWNcdWNkMDggXHViM2M0XHVjMmRjXHViOTdjIFx1YzljMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWQ1NWNcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjOGZkXHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzZjY1x1YjlhY1x1YzViNCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzhcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IE4sIE0sIEsgKDFcdTJhN2QgTiBcdTJhN2QgMzAwLCAwIFx1MmE3ZCBNIFx1MmE3ZCBOKE4tMSksIDEgXHUyYTdkIEsgXHUyYTdkIDEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1ZDZjNCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjIGFcdWM2NDAgYiBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNWYwXHVhY2IwXHVjNzQ0IFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWI0NTBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IGEsIGIgKCAxIFx1MmE3ZCBhICZuZTsgYiBcdTJhN2QgTilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWQ2YzQgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBLXHVhYzFjIFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0ZGNcdWI3OThcdWFjZTQgRGlcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YWMxMiBDaSwgU2ksIE5pICgxIFx1MmE3ZCBDaSBcdTJhN2QgTiwgMSBcdTJhN2QgU2kgXHUyYTdkIDEwXjUsIDAgXHUyYTdkIE5pIFx1MmE3ZCAxMF41KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDAgMCAwXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhY2IwXHVhY2ZjXHViMjk0IFx1YmFhOFx1YjRlMCBcdWI0ZGNcdWI3OThcdWFjZTRcdWM3NDQgXHVjOGZkXHVjNzdjIFx1YzIxOCBcdWM3ODdcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzZjY1x1YjlhY1x1YzViNCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNjA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRHJhZ29ucyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gY2l0aWVzIGFuZCBNIHJvYWRzIGluIERyYWdvbnMgQ291bnRyeS4gQ2l0aWVzIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggTiwgYW5kIGVhY2ggcm9hZCBjb25uZWN0cyBleGFjdGx5IHR3byBjaXRpZXMuIFRoZXJlIGFyZSB0b3RhbGx5IEsgZHJhZ29ucyBEMSwgRDIsIC4gLiAuICwgREsgaW4gdGhlc2UgTiBjaXRpZXMuIERyYWdvbiBEaSBsaXZlcyBpbiBjaXR5IENpIGFuZCBoYXMgaW5pdGlhbGx5IFNpIGhlYWRzLiBJdCBncm93cyBOaSBuZXcgaGVhZHMgZXZlcnkgbWludXRlIHdoaWxlIGFsaXZlISBBIGRyYWdvbiBpcyBhbGl2ZSBpZiBpdCBoYXMgcG9zaXRpdmUgbnVtYmVyIG9mIGhlYWRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSB3YW50IHRvIGhpcmUgYSBudW1iZXIgb2Ygd2FycmlvcnMgdG8ga2lsbCBhbGwgZHJhZ29ucy4gV2Ugc3BlY2lmeSB0aGUgaW5pdGlhbCBjaXR5IG9mIGVhY2ggd2Fycmlvci4gVGhlbiBvbiBlYWNoIG1pbnV0ZSwgZWFjaCB3YXJyaW9yIGNhbiBlaXRoZXIgZ28gdGhyb3VnaCBhIHJvYWQgZnJvbSBoaXMgY3VycmVudCBjaXR5IHRvIGFuIGFkamFjZW50IGNpdHksIG9yIHNlbGVjdCBhbiBhbGl2ZSBkcmFnb24gaW4gaGlzIGN1cnJlbnQgY2l0eSBhbmQgY3V0IG9mZiBvbmUgb2YgaXRzIGhlYWRzLiBXZSBjYW4gc3BlY2lmeSB0aGUgc3RyYXRlZ3kgb2YgZWFjaCB3YXJyaW9yIG9uIGVhY2ggbWludXRlLCBhbmQgYWZ0ZXIgdGhleSBhcmUgZG9uZSwgYW55IGFsaXZlIGRyYWdvbiBEaSB3aWxsIGdyb3cgaXRzIE5pIG5ldyBoZWFkcy48XC9wPlxyXG5cclxuPHA+V2Ugd2FudCB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiB3YXJyaW9ycyB3aXRoIHdoaWNoIGFsbCBkcmFnb25zIGNhbiBiZSBraWxsZWQgaW4gYSBmaW5pdGUgYW1vdW50IG9mIHRpbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSBhcmUgbXVsdGlwbGUgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIE4sIE0gYW5kIEsgKDEgXHUyYTdkIE4gXHUyYTdkIDMwMCwgMCBcdTJhN2QgTSBcdTJhN2QgTihOICZtaW51czsgMSlcLzIsIGFuZCAxIFx1MmE3ZCBLIFx1MmE3ZCAxMDAwKS4gRWFjaCBvZiB0aGUgbmV4dCBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxIFx1MmE3ZCBhICZuZTsmbmJzcDtiIFx1MmE3ZCBOKSBpbmRpY2F0aW5nIGEgcm9hZCBiZXR3ZWVuIGNpdGllcyBhIGFuZCBiLiBUaGUgaS10aCBsaW5lIG9mIHRoZSBuZXh0IEsgbGluZXMgZGVzY3JpYmVzIGRyYWdvbiBEaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBDaSwgU2kgYW5kIE5pICgxIFx1MmE3ZCBDaSBcdTJhN2QgTiwgMSBcdTJhN2QgU2kgXHUyYTdkIDEwPHN1cD41PFwvc3VwPiwgMCBcdTJhN2QgTmkgXHUyYTdkIDEwPHN1cD41PFwvc3VwPikuIFRoZSBpbnB1dCB0ZXJtaW5hdGVzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgMCAwIDAgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHdhcnJpb3JzIHdobyBjYW4gZXZlbnR1YWxseSBraWxsIGFsbCBkcmFnb25zLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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