시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4509 1513 977 31.284%

문제

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

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

입력

첫 번째 줄에는 테스트케이스의 개수 T(1≤T≤5)가 주어진다. 그리고 두 번째 줄부터 T개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1≤N≤500), 도로의 개수 M(1≤M≤2500), 웜홀의 개수(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이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다.

출력

T개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 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
W3sicHJvYmxlbV9pZCI6IjE4NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZGNcdWQ2NDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjU0Y1x1YjI5NCAyMDIwXHViMTQ0LCBcdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNmQ0XHViNGRjXHViMDk4XHViNzdjXHVjNzU4IFx1ZDU1YyBcdWFkNmRcdWJiZmNcdWM3NzRcdWIyZTQuIFx1YzZkNFx1YjRkYyBcdWIwOThcdWI3N2NcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM5YzBcdWM4MTBcdWM3NzQgXHVjNzg4XHVhY2UwIE5cdWFjMWNcdWM3NTggXHVjOWMwXHVjODEwIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YzY0MCBXXHVhYzFjXHVjNzU4IFx1YzZkY1x1ZDY0MFx1Yzc3NCBcdWM3ODhcdWIyZTQuIChcdWIyZTggXHViM2M0XHViODVjXHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWM1YzZcdWM3M2NcdWJhNzAgXHVjNmRjXHVkNjQwXHVjNzQwIFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWM3ODhcdWIyZTQuKSBcdWM2ZGNcdWQ2NDBcdWM3NDAgXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWIzYzRcdWNjMjkgXHVjNzA0XHVjZTU4XHViODVjIFx1YWMwMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2JkXHViODVjXHVjNzc4XHViMzcwLCBcdWQyYjlcdWM3NzRcdWQ1NThcdWFjOGNcdWIzYzQgXHViM2M0XHVjYzI5XHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQgXHVjMmRjXHVjNzkxXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1Yzc0NCBcdWI1NGMgXHViY2Y0XHViMmU0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0YTRcdWI4NWMgXHVhYzAwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNmRjXHVkNjQwIFx1YjBiNFx1YzVkMFx1YzExY1x1YjI5NCBcdWMyZGNcdWFjYzRcdWFjMDAgXHVhYzcwXHVhZmI4XHViODVjIFx1YWMwNFx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM1ZWNcdWIzYzQgXHVjODhiXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWFjMDQgXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVhZDgxXHVhZTA4XHVjODEwXHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC4gMVx1YmM4OCBcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVjNzQ0IFx1ZDU1OFx1YzVlY1x1YzExYyBcdWMyZGNcdWFjMDRcdWM1ZWNcdWQ1ODlcdWM3NDQgXHVkNTU4XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWIyZTRcdWMyZGMgXHVjZDljXHViYzFjXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YjM1OCBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjU0XHVjNzQ0IFx1YjU0YywgXHVjZDljXHViYzFjXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1Yzc0NCBcdWI1NGMgXHViY2Y0XHViMmU0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0MThcdWIzY2NcdWM1NDQgXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc0MCBcdWJjMzFcdWM5MDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1Yzc3NFx1YjdmMCBcdWM3N2NcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjXHVjOWMwIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxJmxlO1QmbGU7NSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgVFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjYzI4XHViODQwXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMFx1YzgxMFx1Yzc1OCBcdWMyMTggTigxJmxlO04mbGU7NTAwKSwgXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOCBNKDEmbGU7TSZsZTsyNTAwKSwgXHVjNmRjXHVkNjQwXHVjNzU4IFx1YWMxY1x1YzIxOCgxJmxlO1cmbGU7MjAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNKzFcdWFjMWNcdWM3NTggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFMsRSxUIFx1YzEzOCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBTXHVjNjQwIEVcdWIyOTQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzljMFx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzgsIFRcdWIyOTQgXHVjNzc0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQxYjVcdWQ1NzQgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgTSsyfk0rVysxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWM2ZGNcdWQ2NDBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFMsRSxUIFx1YzEzOCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFNcdWIyOTQgXHVjMmRjXHVjNzkxIFx1YzljMFx1YzgxMCwgRVx1YjI5NCBcdWIzYzRcdWNjMjkgXHVjOWMwXHVjODEwLCBUXHViMjk0IFx1YzkwNFx1YzViNFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBUXHViMjk0IDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCBcdWI2MTBcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1ZDU1YyBcdWFjMWNcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjOTA0XHVjNWI0XHViNGU0XHViYTc0XHVjMTFjIFx1Y2Q5Y1x1YmMxYyBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQgWUVTLCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4NjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXb3JtaG9sZXMiLCJkZXNjcmlwdGlvbiI6IjxwPldoaWxlIGV4cGxvcmluZyBoaXMgbWFueSBmYXJtcywgRmFybWVyIEpvaG4gaGFzIGRpc2NvdmVyZWQgYSBudW1iZXIgb2YgYW1hemluZyB3b3JtaG9sZXMuIEEgd29ybWhvbGUgaXMgdmVyeSBwZWN1bGlhciBiZWNhdXNlIGl0IGlzIGEgb25lLXdheSBwYXRoIHRoYXQgZGVsaXZlcnMgeW91IHRvIGl0cyBkZXN0aW5hdGlvbiBhdCBhIHRpbWUgdGhhdCBpcyBCRUZPUkUgeW91IGVudGVyZWQgdGhlIHdvcm1ob2xlISBFYWNoIG9mIEZKJiMzOTtzIGZhcm1zIGNvbXByaXNlcyBOICgxICZsdDs9IE4gJmx0Oz0gNTAwKSBmaWVsZHMgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4sIE0gKDEgJmx0Oz0gTSAmbHQ7PSAyNTAwKSBwYXRocywgYW5kIFcgKDEgJmx0Oz0gVyAmbHQ7PSAyMDApIHdvcm1ob2xlcy48XC9wPlxyXG5cclxuPHA+QXMgRkogaXMgYW4gYXZpZCB0aW1lLXRyYXZlbGluZyBmYW4sIGhlIHdhbnRzIHRvIGRvIHRoZSBmb2xsb3dpbmc6IHN0YXJ0IGF0IGZpZWxkIDEsIHRyYXZlbCB0aHJvdWdoIHNvbWUgcGF0aHMgYW5kIHdvcm1ob2xlcywgYW5kIHJldHVybiB0byB0aGUgc3RhcnRpbmcgZmllbGQgYSB0aW1lIGJlZm9yZSBoaXMgaW5pdGlhbCBkZXBhcnR1cmUuIFBlcmhhcHMgaGUgd2lsbCBiZSBhYmxlIHRvIG1lZXQgaGltc2VsZiA6KSAuPFwvcD5cclxuXHJcbjxwPlRvIGhlbHAgRkogZmluZCBvdXQgd2hldGhlciB0aGlzIGlzIHBvc3NpYmxlIG9yIG5vdCwgaGUgd2lsbCBzdXBwbHkgeW91IHdpdGggY29tcGxldGUgbWFwcyB0byBGICgxICZsdDs9IEYgJmx0Oz0gNSkgb2YgaGlzIGZhcm1zLiAmbmJzcDtObyBwYXRocyB3aWxsIHRha2UgbG9uZ2VyIHRoYW4gMTAsMDAwIHNlY29uZHMgdG8gdHJhdmVsIGFuZCBubyB3b3JtaG9sZSBjYW4gYnJpbmcgRkogYmFjayBpbiB0aW1lIGJ5IG1vcmUgdGhhbiAxMCwwMDAgc2Vjb25kcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCBGLiBGIGZhcm0gZGVzY3JpcHRpb25zIGZvbGxvdy48XC9wPlxyXG5cclxuPHA+KiBMaW5lIDEgb2YgZWFjaCBmYXJtOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgcmVzcGVjdGl2ZWx5OiBOLCBNLCBhbmQgVzxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk0rMSBvZiBlYWNoIGZhcm06IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBudW1iZXJzIChTLCBFLCBUKSB0aGF0IGRlc2NyaWJlLCByZXNwZWN0aXZlbHk6IGEgYmlkaXJlY3Rpb25hbCBwYXRoIGJldHdlZW4gUyBhbmQgRSB0aGF0IHJlcXVpcmVzIFQgc2Vjb25kcyB0byB0cmF2ZXJzZS4gVHdvIGZpZWxkcyBtaWdodCBiZSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSBwYXRoLjxcL3A+XHJcblxyXG48cD4qIExpbmVzIE0rMi4uTStXKzEgb2YgZWFjaCBmYXJtOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgbnVtYmVycyAoUywgRSwgVCkgdGhhdCBkZXNjcmliZSwgcmVzcGVjdGl2ZWx5OiBBIG9uZSB3YXkgcGF0aCBmcm9tIFMgdG8gRSB0aGF0IGFsc28gbW92ZXMgdGhlIHRyYXZlbGVyIGJhY2sgVCBzZWNvbmRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZXMgMS4uRjogRm9yIGVhY2ggZmFybSwgb3V0cHV0ICZxdW90O1lFUyZxdW90OyBpZiBGSiBjYW4gYWNoaWV2ZSBoaXMgZ29hbCwgb3RoZXJ3aXNlIG91dHB1dCAmcXVvdDtOTyZxdW90OyAoZG8gbm90IGluY2x1ZGUgdGhlIHF1b3RlcykuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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