Informatica Online Judge

  배고픈 굴라 [1923 / 0783]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs16022 - 28ms / 1454byte
My Best Submission (C++) : N/A

[koistudy.net (34th 김태영)]
Writer ID : [gs16022]

Background

온라인 게임 메이플스토리에는 츄츄 아일랜드라는 지역이 있다. 츄츄 아일랜드는 악당 굴라에 의해 공격을 받고 있고, 착한 주민 무토가 굴라를 막는다. 캐릭터가 강해지기 위해선 이 무토에게 밥을 주는 ‘배고픈 무토’라는 퀘스트를 매일매일 해야한다.

영건이는 강해지고 싶어서 "배고픈 무토" 라는 퀘스트를 한다. 하지만 동준이와 태영이는 영건이가 쎄지는 것은 원하지 않기 때문에, 굴라에게 밥을 주어 영건이를 방해하고 싶다.

N*N 맵에서 동준이는 (1, 1), 태영이는 (N, N) 에 위치하고 있다. 굴라에게 줄 수 있는 밥은 M개가 주어지며, 좌표로 주어진다. 굴라에게 밥을 주기 위해선 굴라가 원하는 밥의 좌표에 동준이나 태영이, 둘 중 한명이 가서 밥을 받은 뒤, 미리 정해놓은 K개의 식탁에 가져놓아야 한다. 이 때, 동준이나 태영이는 움직이는 것을 싫어하기 때문에 가장 적게 이동하고 싶다. 이 때, 굴라에게 밥을 주면서 이동을 최소화 할 수 있게 동준이와 태영이를 도와주자.

예를 들어 굴라의 식탁이 (1, 2), (3, 4)이고 굴라가 (1, 5), (4, 5), (3, 2) 에 있는 밥을 순서대로 먹고 싶다고 하면 동준이가 (1, 1) -> (1, 5) -> (1, 2) 로 가서 첫 번째 밥을 주고, 태영이가 (5, 5) -> (4, 5) -> (3, 4) 로 가서 두 번째 밥을 주고, 태영이가 (3, 4) -> (3, 2) -> (3, 4) 로 가서 세 번째 밥을 주면, 최단거리 14로 굴라의 밥을 모두 줄 수 있다.

Input

첫 번째 줄엔 세 개의 정수 N, M, K 가 입력된다. - N은 맵의 크기, M은 밥의 개수, K는 식탁의 개수
(1 <= N <= 1,000,000,000, 1 <= M <= 100, 1 <= K <= 100)
그 후 M개의 줄에 두 개의 정수 aix aiy가 입력된다. - (aix, aiy) 에 굴라의 I번째 밥이 있다는 의미
(1 <= aix <= N, 1 <= aiy <= N)
그 후 K개의 줄에 두 개의 정수 bix biy 가 입력된다 - (bix, biy) 에 굴라의 I번째 식탁이 있다는 의미

Output

동준이와 태영이가 굴라에게 밥을 주기 위하여 가장 적게 이동하는 최단거리를 출력하여라.

IO Example

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

출력
14

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