시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 388 154 106 40.613%

문제

2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.

두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.

입력

첫째 줄에 도시의 수 N, 텔레포트하는데 걸리는 시간 T가 주어진다.

둘째 줄부터 N개의 줄에 도시의 정보를 의미하는 세 정수 s, x, y가 1번 도시부터 N번 도시까지 순서대로 주어진다. s가 1인 경우에는 특별한 도시라는 의미이고, 0인 경우는 특별한 도시가 아니라는 의미이다. (x, y)는 도시의 좌표이다.

다음 줄에는 M이 주어지고, 다음 M개의 줄에는 두 도시 A와 B가 주어진다. 

출력

총 M개의 줄에 걸쳐서 A에서 B에 가는 최소 이동 시간을 출력한다.

제한

  • 2 ≤ N ≤ 1,000
  • 1 ≤ T ≤ 2,000
  • 1 ≤ M ≤ 1,000
  • 0 ≤ x, y ≤ 1,000
  • A ≠ B
  • 두 도시의 좌표가 같은 경우는 없다.

예제 입력 1

6 3
0 1 2
0 5 1
1 3 3
1 1 5
0 3 5
1 7 5
5
1 2
1 5
1 6
3 4
4 2

예제 출력 1

5
5
6
3
7

예제 입력 2

6 2
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
6
1 2
2 3
3 4
4 5
5 6
6 1

예제 출력 2

1
1
2
1
1
2

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: njw1204