백준 16958번 텔레포트

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

16958번: 텔레포트

 

 

 

 

<접근방법>

특별 도시 사이에는 텔레포트가 가능합니다.

텔레포트가 직접 걸어서 가는 것보다 무조건 빠른 것은 아닙니다. 그러므로 직접 비교해봐야합니다.

따라서 다음과 같은 경우가 발생합니다.

 

1. 일반 -> 일반

 1-1. 걸어간다

 1-2. 특별도시를 거쳐 텔레포트를 이용해서 간다. (일 -> 특 -> 특 -> 일)

 

2. 특별 -> 특별

 2-1. 걸어간다

 2-2. 텔레포트 한다.

 

 

2의 경우는 문제의 조건에 따라 구해주면 됩니다.

 

1-2 의 경우에서 최솟값을 구하기 위해서는 '일반 - 특별' 간의 최솟값이 필요합니다.

 

 

 

---

 

 

 

<코드>

1-2 의 경우에서 최솟값을 구하기 위해서는 '일반 - 특별' 간의 최솟값이 필요합니다.

이를 near배열에 저장합니다.

 

모든 경우를 '일 -> 특 -> 특 -> 일' 로 치환하였으며

'특 -> 특'의 경우 (일 -> 특), (특 -> 일) 이 필요없으므로 near배열에 0을 저장하여 처리하였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct point {
	int y, x, s;
};

const int INF = 987654321;
int n, T, m;
int time[1001][1001];
int near[1001];

vector<point> v;

int gap(int i, int j) {
	return abs(v[i].y - v[j].y) + abs(v[i].x - v[j].x);
}

void from_n_to_s() {
	for (int i = 0; i < n; i++) {
		if (v[i].s == 1) continue;
		near[i] = INF;
		for (int j = 0; j < n; j++) {
			if (v[j].s == 0) continue;
			int just_walk = gap(i, j);
			near[i] = min(near[i], just_walk);
		}
		if (near[i] == INF) near[i] = 0;
	}
}

int main() {
	cin >> n >> T;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({c-1, b-1, a});
	}
    
    //일반도시 -> 특별도시 사이의 최소거리
	from_n_to_s();

	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b, res, just_walk;
		cin >> a >> b;
        just_walk = gap(a-1, b-1);
        
        res = min(just_walk, near[a-1] + T + near[b-1]);
		cout << res << '\n';
	}

	return 0;
}

 

 

 

---