Informatica Online Judge

  시간여행 [1674 / 068A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 54   Total Tried : 313


The Champion of this Problem (C++) : gs16059 - ms / 625byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

한 나라에는 $N$개의 도시가 있고, $N$개의 도시 사이에는 $M$개의 도로(양방향)와 $W$개의 웜홀이 있다.

웜홀은 시작 위치에서 도착 위치로 가는 방향을 가지고 있는 경로로, 웜홀을 통과해 도착을 하면 시작을 하였을 때 보다 시간이 뒤로 가게 된다.

만약 어떤 도시에서 출발을 해서 시간여행을 시작하여 다시 출발을 했던 도시로 돌아왔을 때, 출발을 하였을 때 보다 시간이 되돌아가는 것이 가능한지 불가능한지 알고 싶다.

Input

첫번째 줄에는 도시의 수 $N$, 도로의 개수 $M$, 웜홀의 개수 $W$가 주어진다. 그리고 두번째 줄부터 도로 정보와 웜홀 정보가 순서대로 입력되어 들어온다.

각 도로와 웜홀의 정보는 $s, e, time$ 세 정수로 주어진다. $s$와 $e$는 연결 도시 번호(웜홀은 시작도시, 도착도시), $time$은 이동하는데 걸리는 시간(웜홀은 줄어드는 시간)을 의미한다.

[입력값의 정의역]
$1 ≤ N ≤ 500$
$1 ≤ M ≤ 2500$
$1 ≤ W ≤ 200$

Output

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

IO Example

입력 예1
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3

출력 예1
NO



입력 예 2
3 2 1
1 2 3
2 3 4
3 1 8

출력 예 2
YES

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]