몇 년 간의 추적 끝에 모피어스는 마침내 "그"를 찾아낸다 - 친구에게 네오라는 이름으로 알려진 컴퓨터 프로그래머 토마스 A. 앤더슨을. 당신과 네오는 절친이다. 지역 프로그래밍 대회에 여러 번 같이 출전하기도 했다. 모피어스는 빨간 약을 통해 당신과 네오 모두를 매트릭스에서 구한다. 모피어스의 우주선 네부카드네자르에서 몇 달 간 훈련을 거친 후, 이제 네오가 "그"의 도래를 예언한 오라클을 만날 때다. 네오와 모피어스가 그녀를 만나러 매트릭스로 떠난 동안 당신은 모든 것이 계획대로 진행되도록 현실 세계에 남는다.
오라클을 만난 후, 네오와 모피어스는 매트릭스의 전화기 중 하나를 이용해 현실 세계로 돌아오려 한다. 모피우스가 돌아오고 네오가 전화기를 사용하려 하기 전에, 요원이 전화기를 부숴 네오가 매트릭스에 갇힌다. 아직 네오의 힘이 완전하지 않아, 요원을 만나지 않고 갈 수 있는 가장 가까운 전화기로 달려 요원과 싸우는 것을 피하는 방법밖에 없다.
네부카드네자르의 가장 훌륭한 프로그래머인 당신에게 모피어스는 네오가 요원과 싸워야 할지 말지를 판단하는 프로그램을 작성해 달라고 한다. (요원이 어떻게 움직일지 모르기에 코드는 최악의 상황을 가정해야 한다.) 요원과 전화기의 위치, 각각의 장소로 이동하는 데 필요한 시간이 주어질 때, 만약 네오가 요원을 피할 수 있다면 프로그램은 네오가 언제 매트릭스에서 빠져나올 수 있는지도 판단해야 한다.
만약 네오와 요원이 전화기에 동시에 도착한다면 네오는 전화기를 집기 전에 요원과 싸워야 함에 주의하자.
입력
입력 첫 줄에 테스트 케이스의 수를 나타내는 정수 T(1 <= T <= 100)가 주어진다.
각 테스트 케이스는 네 개의 정수로 이루어진 한 줄로 시작된다: N(3 <= N <= 1000)은 매트릭스에 존재하는 지점의 수, M은 서로 다른 지점을 잇는 도로의 수, NA는 요원의 수, NT는 전화기의 수이다. (NA, NT > 0, NA+NT < N-1)
다음 M개의 줄에는 세 정수 u, v, m이 온다. (0 <= u, v < N, 1 <= m <= 30) 첫 두 정수는 (0으로 표현된 네오의 시작 위치를 포함해) 매트릭스 상 존재하는 지점을 나타내며, 세 번째 정수는 두 지점 사이를 이동하는 데 걸리는 시간을 (분으로) 나타낸다.
[역자 수정 - 다음 줄부터 NA개의 줄에 한 줄에 하나씩 요원의 위치를 나타내는 정수가 주어진다.]
[역자 수정 - 이후 줄부터 NT개의 줄에 한 줄에 하나씩 전화기의 위치를 나타내는 정수가 주어진다.]
(네오의 시작 위치이기도 한) 0번 지점에는 요원도 전화기도 존재하지 않는다. 또한, 전화기와 요원이 처음부터 동시에 존재하는 지점도 없다.
출력
각 테스트에 대해, 네오의 안전을 보장하는 경로가 없을 경우 "Neo may fight an Agent"를 출력한다. 그 외의 경우, 매트릭스를 빠져나오기 위해 필요한 시간을 (분으로) 출력한다.
ez_code 3년 전 3
문제
몇 년 간의 추적 끝에 모피어스는 마침내 "그"를 찾아낸다 - 친구에게 네오라는 이름으로 알려진 컴퓨터 프로그래머 토마스 A. 앤더슨을. 당신과 네오는 절친이다. 지역 프로그래밍 대회에 여러 번 같이 출전하기도 했다. 모피어스는 빨간 약을 통해 당신과 네오 모두를 매트릭스에서 구한다. 모피어스의 우주선 네부카드네자르에서 몇 달 간 훈련을 거친 후, 이제 네오가 "그"의 도래를 예언한 오라클을 만날 때다. 네오와 모피어스가 그녀를 만나러 매트릭스로 떠난 동안 당신은 모든 것이 계획대로 진행되도록 현실 세계에 남는다.
오라클을 만난 후, 네오와 모피어스는 매트릭스의 전화기 중 하나를 이용해 현실 세계로 돌아오려 한다. 모피우스가 돌아오고 네오가 전화기를 사용하려 하기 전에, 요원이 전화기를 부숴 네오가 매트릭스에 갇힌다. 아직 네오의 힘이 완전하지 않아, 요원을 만나지 않고 갈 수 있는 가장 가까운 전화기로 달려 요원과 싸우는 것을 피하는 방법밖에 없다.
네부카드네자르의 가장 훌륭한 프로그래머인 당신에게 모피어스는 네오가 요원과 싸워야 할지 말지를 판단하는 프로그램을 작성해 달라고 한다. (요원이 어떻게 움직일지 모르기에 코드는 최악의 상황을 가정해야 한다.) 요원과 전화기의 위치, 각각의 장소로 이동하는 데 필요한 시간이 주어질 때, 만약 네오가 요원을 피할 수 있다면 프로그램은 네오가 언제 매트릭스에서 빠져나올 수 있는지도 판단해야 한다.
만약 네오와 요원이 전화기에 동시에 도착한다면 네오는 전화기를 집기 전에 요원과 싸워야 함에 주의하자.
입력
입력 첫 줄에 테스트 케이스의 수를 나타내는 정수 T(1 <= T <= 100)가 주어진다.
각 테스트 케이스는 네 개의 정수로 이루어진 한 줄로 시작된다: N(3 <= N <= 1000)은 매트릭스에 존재하는 지점의 수, M은 서로 다른 지점을 잇는 도로의 수, NA는 요원의 수, NT는 전화기의 수이다. (NA, NT > 0, NA+NT < N-1)
다음 M개의 줄에는 세 정수 u, v, m이 온다. (0 <= u, v < N, 1 <= m <= 30) 첫 두 정수는 (0으로 표현된 네오의 시작 위치를 포함해) 매트릭스 상 존재하는 지점을 나타내며, 세 번째 정수는 두 지점 사이를 이동하는 데 걸리는 시간을 (분으로) 나타낸다.
[역자 수정 - 다음 줄부터 NA개의 줄에 한 줄에 하나씩 요원의 위치를 나타내는 정수가 주어진다.]
[역자 수정 - 이후 줄부터 NT개의 줄에 한 줄에 하나씩 전화기의 위치를 나타내는 정수가 주어진다.]
(네오의 시작 위치이기도 한) 0번 지점에는 요원도 전화기도 존재하지 않는다. 또한, 전화기와 요원이 처음부터 동시에 존재하는 지점도 없다.
출력
각 테스트에 대해, 네오의 안전을 보장하는 경로가 없을 경우 "Neo may fight an Agent"를 출력한다. 그 외의 경우, 매트릭스를 빠져나오기 위해 필요한 시간을 (분으로) 출력한다.