[BOJ/Gold 5] 백준 16958 텔레포트(C++)

문제 링크

https://www.acmicpc.net/problem/16958

16958번: 텔레포트

문제

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

알고리즘 분류

• 최단 거리 알고리즘

풀이

각 도시마다 이동 시간을 구하고, 두 도시가 특별한 도시라면 일반적인 이동 시간과 텔레포트했을 때의 시간(T) 중 최솟값으로 설정한다. 그리고 플로이드-와샬 알고리즘을 사용하여 최단 경로를 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	bool S;
	int Y, X;
};

int N, T, M;
vector<INFO> Vec;
int DP[MAX][MAX];
int Small = 5000;
vector<int> Candidate;

void init() {
	Vec.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				continue;
			}
			DP[i][j] = INF;
		}
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				continue;
			}
			if (Vec[i].S && Vec[j].S) {
				DP[i][j] = min(T, abs(Vec[i].Y - Vec[j].Y) + abs(Vec[i].X - Vec[j].X));
			}
			else {
				DP[i][j] = abs(Vec[i].Y - Vec[j].Y) + abs(Vec[i].X - Vec[j].X);
			}
		}
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (DP[i][j] > DP[i][k] + DP[k][j]) {
					DP[i][j] = DP[i][k] + DP[k][j];
				}
			}
		}
	}
}

int main() {
	FIRST
	cin >> N >> T;
	init();
	for (int i = 1; i <= N; i++) {
		cin >> Vec[i].S >> Vec[i].Y >> Vec[i].X;
	}
	Settings();
	cin >> M;
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		cout << DP[A][B] << "\n";
	}

	return 0;
}