Informatica Online Judge

  남작님의 연회 [2115 / 0843]

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


The Champion of this Problem (C++) : gs16106 - 0ms / 805byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16095]

Background

W 남작은 친척들의 등쌀에 떠밀려 본인의 생일 연회를 열게 되었다.

하지만 게으른 남작은 연회 따위 열고 싶지 않으며, 되도록이면 모든 손님들이 연회장으로 오기도 전에 집으로 돌아가 버리기를 바란다.

손님들은 각각 출발지로부터 일정 거리 이하로 떨어진 연회장에만 갈 수 있으며, 그들은 똑똑하며 연회에 몹시 가고 싶어 하기 때문에 최단 경로를 따라서만 움직인다.

남작을 도와 이 연회가 파토날 수 있도록 연회장을 골라보자. (두 지점 사이의 도로는 양방향 통행이 가능하다.)

Input

첫 번째 줄에는 연회에 초대하는 손님의 수 M과 연회장의 개수 N, 경로의 개수 O가 입력된다. M, N, O는 1 이상 100 이하의 자연수이다.

이후 M줄에 걸쳐 각 손님의 출발지 I와 최대로 갈 수 있는 거리 J가 주어진다. I는 1 이상 M 이하의 자연수이며, J는 1 이상 100 이하의 자연수이다.

다음 N줄에 걸쳐 연회장의 위치 L이 입력된다. L은 1 이상 M 이하의 자연수이다.

이후 O줄에 걸쳐 출발지 S와 도착지 E, 두 지점 사이의 거리 D가 주어진다. D는 1 이상 100 이하의 자연수이며, S, E는 1 이상 M 이하의 자연수이다.

Output

첫 번째 줄에 연회장을 찾아올 수 있는 최소 인원수를 출력한다.

만약 아무도 연회장을 찾아오지 못하게 만들 수 있다면 남작의 기쁨을 담아 “SUCCESS!"를 출력한다. (큰 따옴표는 출력하지 않는다.)

IO Example

입력
4 2 4
2 3
3 5
4 2
4 1
1
3
1 2 4
1 4 3
2 3 2
2 4 4

출력
SUCCESS!

입력
6 3 5
1 2
1 3
2 6
2 4
3 5
4 5
1
3
4
1 2 3
1 3 3
2 3 5
2 4 4
3 4 2

출력
4

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