백준 (BOJ) 16958번 텔레포트

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

16958번: 텔레포트

 

풀이 :

 

우선 2차원 행렬인 dist를 통해 A와 B의 거리를 계산해 놓는다.

 

그리고 직접 가는 방법 A -> B에 값을 구한다. 이때 A와 B가 둘 다 특별한 도시라면 T로 갱신할 수

 

있는지 체크해주어야 한다.

 

이제 더 작아질 수 경우는 A,B에 가장 가까운 곳을 방문해서 T를 이용해 가는 방법이다.

 

해당 경우가 더 작아지면 갱신해주게 된다.

 

 

코드 ( C++ )

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int n, t, m;
	int x[1000];
	int y[1000];
	int isSpecial[1000];
	int dist[1001][1001];
	int near(int x) {
	int ret = -1;
	int minIdx = -1;
	for (int i = 0; i < n; ++i) {
	if (isSpecial[i] == 0) continue;
	if (ret == -1 || ret > dist[x][i]) {
	ret = dist[x][i];
	minIdx = i;
	}
	}
	return minIdx;
	}
	int findTheLength(int a, int b) {
	int directLength = dist[a][b];
	// 둘다 특별한 도시라면
	if (isSpecial[a] == 1 && isSpecial[b] == 1)
	directLength = min(directLength, t);
	// 가장 가까운 거리
	int nearA = near(a);
	int nearB = near(b);
	// 한번에 가는 것과 거쳤다 오는 것에 최소
	if (nearA != -1 && nearB != -1) {
	directLength = min(directLength, dist[a][nearA] + t + dist[nearB][b]);
	}
	return directLength;
	}
	int main()
	{
	cin >> n >> t;
	for (int i = 0; i < n; ++i) {
	cin >> isSpecial[i] >> x[i] >> y[i];
	}
	// 미리 모든 dist를 구해놓는다.
	for (int i = 0; i < n; ++i) {
	for (int j = i+1; j < n; ++j) {
	dist[i][j] = dist[j][i] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
	}
	}
	int m;
	cin >> m;
	for (int i = 0; i < m; ++i) {
	int a, b;
	cin >> a >> b;
	a -= 1; b -= 1;
	cout << findTheLength(a, b) << "\n";
	}
	}

view raw .cpp hosted with ❤ by GitHub