시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4764 1592 1032 31.056%

문제

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 1번 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다. 그리고 두 번째 줄부터 M+1개의 줄까지 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다. 그리고 M+2~M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다. T는 10,000보다 작거나 같은 자연수 또는 0이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

출력

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

예제 입력 1

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

예제 출력 1

NO
YES
W3sicHJvYmxlbV9pZCI6IjE4NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZGNcdWQ2NDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjU0Y1x1YjI5NCAyMDIwXHViMTQ0LCBcdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNmQ0XHViNGRjXHViMDk4XHViNzdjXHVjNzU4IFx1ZDU1YyBcdWFkNmRcdWJiZmNcdWM3NzRcdWIyZTQuIFx1YzZkNFx1YjRkY1x1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzljMFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWFjZTAgTlx1YWMxY1x1Yzc1OCBcdWM5YzBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHVjNjQwIFdcdWFjMWNcdWM3NTggXHVjNmRjXHVkNjQwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gKFx1YjJlOCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IFx1YzVjNlx1YzczY1x1YmE3MCBcdWM2ZGNcdWQ2NDBcdWM3NDAgXHViYzI5XHVkNWE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4pIFx1YzZkY1x1ZDY0MFx1Yzc0MCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2MyOSBcdWM3MDRcdWNlNThcdWI4NWMgXHVhYzAwXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWM3NzhcdWIzNzAsIFx1ZDJiOVx1Yzc3NFx1ZDU1OFx1YWM4Y1x1YjNjNCBcdWIzYzRcdWNjMjlcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCBcdWMyZGNcdWM3OTFcdWM3NDQgXHVkNTU4XHVjNjAwXHVjNzQ0IFx1YjU0Y1x1YmNmNFx1YjJlNCBcdWMyZGNcdWFjMDRcdWM3NzQgXHViNGE0XHViODVjIFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzZkY1x1ZDY0MCBcdWIwYjRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjMmRjXHVhY2M0XHVhYzAwIFx1YWM3MFx1YWZiOFx1Yjg1YyBcdWFjMDRcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNWVjXHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhYzA0IFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI5ZTRcdWM2YjAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YWQ4MVx1YWUwOFx1Yzk5ZFx1YzVkMCBcdWJlNjBcdWM4NGNcdWIyZTQuIDFcdWJjODggXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1Yzc0NCBcdWQ1NThcdWM1ZWNcdWMxMWMgXHVjMmRjXHVhYzA0XHVjNWVjXHVkNTg5XHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHViMmU0XHVjMmRjIFx1Y2Q5Y1x1YmMxY1x1Yzc0NCBcdWQ1NThcdWM2MDBcdWIzNTggXHVjNzA0XHVjZTU4XHViODVjIFx1YjNjY1x1YzU0NFx1YzY1NFx1Yzc0NCBcdWI1NGMsIFx1Y2Q5Y1x1YmMxY1x1Yzc0NCBcdWQ1NThcdWM2MDBcdWM3NDQgXHViNTRjXHViY2Y0XHViMmU0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0MThcdWIzY2NcdWM1NDRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHVjNWVjXHViN2VjXHViZDg0XHVjNzQwIFx1YmMzMVx1YzkwMFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjNzc0XHViN2YwIFx1Yzc3Y1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWNcdWM5YzAgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUQygxICZsZTsgVEMgJmxlOyA1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBUQ1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjYzI4XHViODQwXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMFx1YzgxMFx1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDUwMCksIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMTggTSgxICZsZTsgTSAmbGU7IDI1MDApLCBcdWM2ZGNcdWQ2NDBcdWM3NTggXHVhYzFjXHVjMjE4IFcoMSAmbGU7IFcgJmxlOyAyMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE0rMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWFlNGNcdWM5YzAgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgUywgRSwgVCBcdWMxMzggXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gU1x1YzY0MCBFXHViMjk0IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWM5YzBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4LCBUXHViMjk0IFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIE0rMn5NK1crMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVjNmRjXHVkNjQwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBTLCBFLCBUIFx1YzEzOCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFNcdWIyOTQgXHVjMmRjXHVjNzkxIFx1YzljMFx1YzgxMCwgRVx1YjI5NCBcdWIzYzRcdWNjMjkgXHVjOWMwXHVjODEwLCBUXHViMjk0IFx1YzkwNFx1YzViNFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBUXHViMjk0IDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCBcdWI2MTBcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1ZDU1YyBcdWFjMWNcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjg1YyBcdWM5MTFcdWJjZjUgXHVjNWM2XHVjNzc0IFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VENcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzkwNFx1YzViNFx1YjRlNFx1YmE3NFx1YzExYyBcdWNkOWNcdWJjMWMgXHVjNzA0XHVjZTU4XHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0IFlFUywgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViYTc0IE5PXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODY1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV29ybWhvbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5XaGlsZSBleHBsb3JpbmcgaGlzIG1hbnkgZmFybXMsIEZhcm1lciBKb2huIGhhcyBkaXNjb3ZlcmVkIGEgbnVtYmVyIG9mIGFtYXppbmcgd29ybWhvbGVzLiBBIHdvcm1ob2xlIGlzIHZlcnkgcGVjdWxpYXIgYmVjYXVzZSBpdCBpcyBhIG9uZS13YXkgcGF0aCB0aGF0IGRlbGl2ZXJzIHlvdSB0byBpdHMgZGVzdGluYXRpb24gYXQgYSB0aW1lIHRoYXQgaXMgQkVGT1JFIHlvdSBlbnRlcmVkIHRoZSB3b3JtaG9sZSEgRWFjaCBvZiBGSiYjMzk7cyBmYXJtcyBjb21wcmlzZXMgTiAoMSAmbHQ7PSBOICZsdDs9IDUwMCkgZmllbGRzIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OLCBNICgxICZsdDs9IE0gJmx0Oz0gMjUwMCkgcGF0aHMsIGFuZCBXICgxICZsdDs9IFcgJmx0Oz0gMjAwKSB3b3JtaG9sZXMuPFwvcD5cclxuXHJcbjxwPkFzIEZKIGlzIGFuIGF2aWQgdGltZS10cmF2ZWxpbmcgZmFuLCBoZSB3YW50cyB0byBkbyB0aGUgZm9sbG93aW5nOiBzdGFydCBhdCBmaWVsZCAxLCB0cmF2ZWwgdGhyb3VnaCBzb21lIHBhdGhzIGFuZCB3b3JtaG9sZXMsIGFuZCByZXR1cm4gdG8gdGhlIHN0YXJ0aW5nIGZpZWxkIGEgdGltZSBiZWZvcmUgaGlzIGluaXRpYWwgZGVwYXJ0dXJlLiBQZXJoYXBzIGhlIHdpbGwgYmUgYWJsZSB0byBtZWV0IGhpbXNlbGYgOikgLjxcL3A+XHJcblxyXG48cD5UbyBoZWxwIEZKIGZpbmQgb3V0IHdoZXRoZXIgdGhpcyBpcyBwb3NzaWJsZSBvciBub3QsIGhlIHdpbGwgc3VwcGx5IHlvdSB3aXRoIGNvbXBsZXRlIG1hcHMgdG8gRiAoMSAmbHQ7PSBGICZsdDs9IDUpIG9mIGhpcyBmYXJtcy4gJm5ic3A7Tm8gcGF0aHMgd2lsbCB0YWtlIGxvbmdlciB0aGFuIDEwLDAwMCBzZWNvbmRzIHRvIHRyYXZlbCBhbmQgbm8gd29ybWhvbGUgY2FuIGJyaW5nIEZKIGJhY2sgaW4gdGltZSBieSBtb3JlIHRoYW4gMTAsMDAwIHNlY29uZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgRi4gRiBmYXJtIGRlc2NyaXB0aW9ucyBmb2xsb3cuPFwvcD5cclxuXHJcbjxwPiogTGluZSAxIG9mIGVhY2ggZmFybTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHJlc3BlY3RpdmVseTogTiwgTSwgYW5kIFc8XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5NKzEgb2YgZWFjaCBmYXJtOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgbnVtYmVycyAoUywgRSwgVCkgdGhhdCBkZXNjcmliZSwgcmVzcGVjdGl2ZWx5OiBhIGJpZGlyZWN0aW9uYWwgcGF0aCBiZXR3ZWVuIFMgYW5kIEUgdGhhdCByZXF1aXJlcyBUIHNlY29uZHMgdG8gdHJhdmVyc2UuIFR3byBmaWVsZHMgbWlnaHQgYmUgY29ubmVjdGVkIGJ5IG1vcmUgdGhhbiBvbmUgcGF0aC48XC9wPlxyXG5cclxuPHA+KiBMaW5lcyBNKzIuLk0rVysxIG9mIGVhY2ggZmFybTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIG51bWJlcnMgKFMsIEUsIFQpIHRoYXQgZGVzY3JpYmUsIHJlc3BlY3RpdmVseTogQSBvbmUgd2F5IHBhdGggZnJvbSBTIHRvIEUgdGhhdCBhbHNvIG1vdmVzIHRoZSB0cmF2ZWxlciBiYWNrIFQgc2Vjb25kcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmVzIDEuLkY6IEZvciBlYWNoIGZhcm0sIG91dHB1dCAmcXVvdDtZRVMmcXVvdDsgaWYgRkogY2FuIGFjaGlldmUgaGlzIGdvYWwsIG90aGVyd2lzZSBvdXRwdXQgJnF1b3Q7Tk8mcXVvdDsgKGRvIG5vdCBpbmNsdWRlIHRoZSBxdW90ZXMpLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO December 2006 Contest > Gold 1번