[백준/BOJ] 백준 2472번 : 체인점

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

2472번: 체인점

 

각 아파트로부터 각 매장 후보지까지 최단 거리를 구하고, 후보지 번호를 A 아파트로부터 거리 순으로 정렬한 뒤 A 아파트로부터 거리가 짧은 후보지부터 매장을 설치할 수 있는지 확인했다.

 

후보지가 매장을 설치할 수 있는지 확인하기 위해서 해당 후보지가 다른 후보지보다 A, B, C 아파트와의 거리가 모두 긴 경우가 있지 않은지 확인해야 했는데, 우선 A 아파트와의 거리 비교는 A 아파트와의 거리가 짧은 후보지부터 매장을 설치할 수 있는지 확인하므로 지금 확인하는 것보다 뒤에 확인하는 후보지들은 해당 후보지보다 A 아파트와의 거리가 짧을 수 없음을 확인하여, 해당 후보지 보다 앞서 확인한 후보지들 중 B 아파트와의 거리 그리고 C 아파트와의 거리가 짧은 게 있었는지 확인해야 했다.

 

이때, 앞서 확인한 후보지들 순서로 "[B아파트 단지까지 거리 순위] = C아파트 단지까지 거리 최솟값"으로 만든 세그먼트 트리를 업데이트해 나아가며 앞서 기록된 후보지들 중 확인하는 후보지의 B 아파트와의 거리 순위 이하 범위의 세그먼트 트리 쿼리를 통해 A 아파트와의 거리가 짧은 후보지들 중 B 아파트와의 거리 그리고 C 아파트와의 거리가 짧은 게 있는지 확인하는 방법을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <limits>
#include <tuple>
using namespace std;

int n;
vector<int> aparts;
int m;
int t;
vector<long long> min_sgmtt(4 * 100005, numeric_limits<long long>::max()); //[B아파트 단지까지 거리 순위] = C아파트 단지까지 거리 최솟값으로 만든 세그먼트트리

//[아파트단지][매장 후보지] = 아파트단지에서 매장 후보지까지 최단 거리
vector<vector<long long>> short_dist(3, vector<long long>(100005, numeric_limits<long long>::max()));

vector<pair<long long, int>> adj[100005];
vector<string> result(100005);

long long UpdateMinSgmtt(int here, int range_left, int range_right, int b_rank, long long c_dist) {

	if (range_left == range_right && range_right == b_rank) {
		return min_sgmtt[here] = min(min_sgmtt[here], c_dist);
	}

	if (b_rank < range_left || range_right < b_rank) {
		return min_sgmtt[here];
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;

	return min_sgmtt[here] = min(UpdateMinSgmtt(left_child, range_left, mid, b_rank, c_dist), UpdateMinSgmtt(right_child, mid + 1, range_right, b_rank, c_dist));
}

long long QueryMinSgmtt(int here, int range_left, int range_right, int find_left, int find_right) {

	if (find_left <= range_left && range_right <= find_right) {
		return min_sgmtt[here];
	}

	if (range_right < find_left || find_right < range_left) {
		return numeric_limits<long long>::max();
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;

	return min(QueryMinSgmtt(left_child, range_left, mid, find_left, find_right), QueryMinSgmtt(right_child, mid + 1, range_right, find_left, find_right));
}

void FindShort(int apart, int start) {
	priority_queue<pair<long long, int>> pq;

	short_dist[apart][start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty()) {
		int here = pq.top().second;
		long long here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_dist[apart][here]) {
			continue;
		}

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].second;
			long long there_cost = here_cost + adj[here][i].first;

			if (short_dist[apart][there] > there_cost) {
				short_dist[apart][there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < 3; i++) {
		int input;
		cin >> input;

		aparts.push_back(input);
	}

	cin >> m;

	for (int i = 0; i < m; i++) {
		int x, y;
		long long z;
		cin >> x >> y >> z;

		adj[x].push_back(make_pair(z, y));
		adj[y].push_back(make_pair(z, x));
	}

	//각 아파트로 부터 각 매장 후보지까지 최단 거리를 구한다
	for (int i = 0; i < 3; i++) {
		FindShort(i, aparts[i]);
	}

	vector<tuple<long long, long long, long long, int>> dist_info; //각 지점에서 A,B,C 아파트까지 최단 거리와 각 지점 번호 저장
	vector<long long> b_dist_info; //각 지점에서 B아파트 까지 최단 거리를 저장
	for (int i = 1; i <= n; i++) {
		dist_info.push_back(make_tuple(short_dist[0][i], short_dist[1][i], short_dist[2][i], i));
		b_dist_info.push_back(short_dist[1][i]);
	}

	sort(dist_info.begin(), dist_info.end()); //A아파트까지 거리 순으로 정렬

	//각 지점에서 B아파트까지 최단 거리를 정렬하고, 중복된 숫자 제거
	//각 지점에서 B아파트까지 거리의 순위를 매기기 위해 사용
	//순위로 하지 않고 거리값 자체를 인덱스로 하는 세그먼트 트리를 만드려고 하면 메모리가 너무 커짐 (최대 (100000(N) * 5(지점에 연결된 도로의 개수) / 2) * 10000(도로의 길이))
	sort(b_dist_info.begin(), b_dist_info.end());
	b_dist_info.erase(unique(b_dist_info.begin(), b_dist_info.end()), b_dist_info.end());

	vector<pair<int, long long>> update_info;

	for (int i = 0; i < n; i++) {

		long long a_dist = get<0>(dist_info[i]);
		long long b_dist = get<1>(dist_info[i]);
		long long c_dist = get<2>(dist_info[i]);
		int number = get<3>(dist_info[i]); //매장 후보지 번호

		int b_rank = lower_bound(b_dist_info.begin(), b_dist_info.end(), b_dist) - b_dist_info.begin(); //B아파트까지 거리 순위 (0~n-1)

		if (i == 0) {
			result[number] = "YES"; //A아파트와 거리가 가장 짧은 지점일때. 즉 다른 어떤 후보지 보다도 A아파트와의 거리가 짧을때
		}

		else if (b_rank == 0) { //B아파트와 거리가 가장 짧은 지점일때. 즉 다른 어떤 후보지 보다도 B아파트와의 거리가 짧을때
			result[number] = "YES";
		}

		//이미 세그먼트트리에 이전에 기록된 값은 해당 지점보다 A아파트 까지의 거리가 짧은 지점이라는 것을 의미
		//이 중에서 B아파트 까지의 거리가 짧은 것 중 C아파트 까지 거리가 짧은게 있는지 확인
		else if (QueryMinSgmtt(0, 0, n - 1, 0, b_rank - 1) < c_dist) {
			result[number] = "NO";
		}

		else {
			result[number] = "YES";
		}

		update_info.push_back(make_pair(b_rank, c_dist));

		//세그먼트 트리를 업데이트 해야 되는 시점일때 
		//A아파트까지 거리가 같은것을 세그먼트 트리에 같은 시점에 기록해야, 이전에 기록된것이 A아파트 까지 거리가 더 짧은것임을 보장할 수 있다
		if (i == n - 1 || a_dist != get<0>(dist_info[i + 1])) {

			//세그먼트 트리에 기록
			for (int j = 0; j < update_info.size(); j++) {
				UpdateMinSgmtt(0, 0, n - 1, update_info[j].first, update_info[j].second);
			}
			update_info.clear();
		}
	}

	cin >> t;

	for (int i = 0; i < t; i++) {
		int q;
		cin >> q;

		cout << result[q] << "\n";
	}

	return 0;
}