시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 100 28 23 30.263%

문제

드래곤 나라에는 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+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBOLCBNLCBLICgxXHUyYTdkIE4gXHUyYTdkIDMwMCwgMCBcdTJhN2QgTSBcdTJhN2QgTihOLTEpLCAxIFx1MmE3ZCBLIFx1MmE3ZCAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkYyBhXHVjNjQwIGIgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzVmMFx1YWNiMFx1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiICggMSBcdTJhN2QgYSAmbmU7IGIgXHUyYTdkIE4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVkNmM0IEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gS1x1YWMxYyBcdWM5MDRcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGRjXHViNzk4XHVhY2U0IERpXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFjMTIgQ2ksIFNpLCBOaSAoMSBcdTJhN2QgQ2kgXHUyYTdkIE4sIDEgXHUyYTdkIFNpIFx1MmE3ZCAxMF41LCAwIFx1MmE3ZCBOaSBcdTJhN2QgMTBeNSlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAwIDAgMFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MThcdWJhNzQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWNiMFx1YWNmY1x1YjI5NCBcdWJhYThcdWI0ZTAgXHViNGRjXHViNzk4XHVhY2U0XHVjNzQ0IFx1YzhmZFx1Yzc3YyBcdWMyMTggXHVjNzg3XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM2Y2NcdWI5YWNcdWM1YjQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDYwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRyYWdvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBOIGNpdGllcyBhbmQgTSByb2FkcyBpbiBEcmFnb25zIENvdW50cnkuIENpdGllcyBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIE4sIGFuZCBlYWNoIHJvYWQgY29ubmVjdHMgZXhhY3RseSB0d28gY2l0aWVzLiBUaGVyZSBhcmUgdG90YWxseSBLIGRyYWdvbnMgRDEsIEQyLCAuIC4gLiAsIERLIGluIHRoZXNlIE4gY2l0aWVzLiBEcmFnb24gRGkgbGl2ZXMgaW4gY2l0eSBDaSBhbmQgaGFzIGluaXRpYWxseSBTaSBoZWFkcy4gSXQgZ3Jvd3MgTmkgbmV3IGhlYWRzIGV2ZXJ5IG1pbnV0ZSB3aGlsZSBhbGl2ZSEgQSBkcmFnb24gaXMgYWxpdmUgaWYgaXQgaGFzIHBvc2l0aXZlIG51bWJlciBvZiBoZWFkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugd2FudCB0byBoaXJlIGEgbnVtYmVyIG9mIHdhcnJpb3JzIHRvIGtpbGwgYWxsIGRyYWdvbnMuIFdlIHNwZWNpZnkgdGhlIGluaXRpYWwgY2l0eSBvZiBlYWNoIHdhcnJpb3IuIFRoZW4gb24gZWFjaCBtaW51dGUsIGVhY2ggd2FycmlvciBjYW4gZWl0aGVyIGdvIHRocm91Z2ggYSByb2FkIGZyb20gaGlzIGN1cnJlbnQgY2l0eSB0byBhbiBhZGphY2VudCBjaXR5LCBvciBzZWxlY3QgYW4gYWxpdmUgZHJhZ29uIGluIGhpcyBjdXJyZW50IGNpdHkgYW5kIGN1dCBvZmYgb25lIG9mIGl0cyBoZWFkcy4gV2UgY2FuIHNwZWNpZnkgdGhlIHN0cmF0ZWd5IG9mIGVhY2ggd2FycmlvciBvbiBlYWNoIG1pbnV0ZSwgYW5kIGFmdGVyIHRoZXkgYXJlIGRvbmUsIGFueSBhbGl2ZSBkcmFnb24gRGkgd2lsbCBncm93IGl0cyBOaSBuZXcgaGVhZHMuPFwvcD5cclxuXHJcbjxwPldlIHdhbnQgdG8gZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2Ygd2FycmlvcnMgd2l0aCB3aGljaCBhbGwgZHJhZ29ucyBjYW4gYmUga2lsbGVkIGluIGEgZmluaXRlIGFtb3VudCBvZiB0aW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgYXJlIG11bHRpcGxlIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBOLCBNIGFuZCBLICgxIFx1MmE3ZCBOIFx1MmE3ZCAzMDAsIDAgXHUyYTdkIE0gXHUyYTdkIE4oTiAmbWludXM7IDEpXC8yLCBhbmQgMSBcdTJhN2QgSyBcdTJhN2QgMTAwMCkuIEVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgYSBhbmQgYiAoMSBcdTJhN2QgYSAmbmU7Jm5ic3A7YiBcdTJhN2QgTikgaW5kaWNhdGluZyBhIHJvYWQgYmV0d2VlbiBjaXRpZXMgYSBhbmQgYi4gVGhlIGktdGggbGluZSBvZiB0aGUgbmV4dCBLIGxpbmVzIGRlc2NyaWJlcyBkcmFnb24gRGkgd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgQ2ksIFNpIGFuZCBOaSAoMSBcdTJhN2QgQ2kgXHUyYTdkIE4sIDEgXHUyYTdkIFNpIFx1MmE3ZCAxMDxzdXA+NTxcL3N1cD4sIDAgXHUyYTdkIE5pIFx1MmE3ZCAxMDxzdXA+NTxcL3N1cD4pLiBUaGUgaW5wdXQgdGVybWluYXRlcyB3aXRoIGEgbGluZSBjb250YWluaW5nIDAgMCAwIHdoaWNoIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiB3YXJyaW9ycyB3aG8gY2FuIGV2ZW50dWFsbHkga2lsbCBhbGwgZHJhZ29ucy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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