Black Hole(블랙홀) > 문제은행

본문 바로가기


알고리즘 자료구조2

2223 : Black Hole(블랙홀)

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 43 회    시도횟수: 203 회   



농부 창호는 자신의 농지에서 블랙홀을 발견했다. 블랙홀에 들어가면 다른 농지로 이동할 수 있는데, 이 경우 시간이 거꾸로 흘러갈 수 있다.

창호의 농지는 N(1<=N<=500)개의 영역으로 구성되어있다. 영역들은 1번부터 N번으로 번호가 매겨져 있으며 M(1<=M<=2,500)개의 평범한 이동경로(간선)가 존재한다.

그리고 B(1<=B<=200)개의 블랙홀이 있다. 창호는 이 블랙홀들을 이용해서 시간을 거꾸로 돌리고 싶다. 다시 말해서, 한 농지 영역에서 출발하여 다시 출발했던 영역으로 돌아왔을 때의 시간이 과거가 되게 하려 한다. 이것이 가능한지 판단하는 프로그램을 작성하라.


첫째 줄에는 테스트케이스 수 F(1<=F<=5)가 입력된다.

매 입력 케이스의 첫 줄에는 N, M, B가 입력된다.

다음 M개의 줄에 걸쳐 각 줄마다 S, E, T 세 개의 정수가 입력된다. 이동경로(간선)의 두 농지영역(노드)S, E와 이동하는데 걸리는 시간 T( 0 <= T <= 10,000)가 주어진다. 평범한 이동경로는 양방향이다.

다음 B개의 줄에 걸쳐 각 줄마다 S, E, T 세 개의 정수가 주어진다. 블랙홀은 단방향이며 S에서 E로 이동하는데 T( 0 <= T <= 10,000)만큼 시간이 거꾸로 가는 것을 의미한다.



매 테스트 케이스마다 과거로의 시간 여행이 가능한지 여부를 출력한다.


[Copy]
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
[Copy]
NO
YES





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.