취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2472번 문제인 체인점이다.
문제는 아래 링크를 확인하자.

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

각 장소에서 A, B, C까지의 거리는 dijkstra 알고리즘으로 간단히 구할 수 있다.

거리의 값의 범위가 매우 넓으므로 중복값에 유의하여 좌표압축을 해주자.

각 장소에서 A까지의 거리들에 중복값이 없고, B와 C에 대해서도 마찬가지였다면 #2336과 같은 문제가 된다.

이 문제에는 중복값이 있으므로, 이 점에 유의하여 구현하자.

아래는 제출한 소스코드이다.

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

struct point {
	int idx, distA, distB, distC;
};

bool compA(point p1, point p2) {
	return p1.distA < p2.distA;
}

bool compB(point p1, point p2) {
	return p1.distB < p2.distB;
}

bool compC(point p1, point p2) {
	return p1.distC < p2.distC;
}

point p[100001];
vector<pair<int, int>> G[100001];
int visited[100001];
int dist[100001];

int seg[262145];

void init(int L, int R, int sI) {
	seg[sI] = 1000000007;
	if (L < R) {
		init(L, (L + R) / 2, sI * 2);
		init((L + R) / 2 + 1, R, sI * 2 + 1);
	}
}

int update(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = min(seg[sI], qVal);
	return seg[sI] = min(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int rangemin(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 1000000007;
	if (qL <= L && R <= qR) return seg[sI];
	return min(rangemin(L, (L + R) / 2, qL, qR, sI * 2), rangemin((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

void dijkstra(int s) {
	priority_queue<pair<int, int>> pq;
	pq.push({ -1,s });
	while (!pq.empty()) {
		int current = pq.top().second, d = -pq.top().first; pq.pop();
		if (visited[current]) continue;
		visited[current] = 1;
		dist[current] = d;
		for (auto node : G[current]) {
			if (visited[node.second]) continue;
			pq.push({ -(d + node.first),node.second });
		}
	}
}

int ans[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, A, B, C, M; cin >> N >> A >> B >> C >> M;
	
	while (M--) {
		int x, y, z; cin >> x >> y >> z;
		G[x].push_back({ z,y });
		G[y].push_back({ z,x });
	}

	for (int i = 1; i <= N; i++) p[i].idx = i;

	dijkstra(A);
	for (int i = 1; i <= N; i++) p[i].distA = dist[i];
	memset(visited, 0, sizeof(visited));
	memset(dist, 0, sizeof(dist));
	dijkstra(B);
	for (int i = 1; i <= N; i++) p[i].distB = dist[i];
	memset(visited, 0, sizeof(visited));
	memset(dist, 0, sizeof(dist));
	dijkstra(C);
	for (int i = 1; i <= N; i++) p[i].distC = dist[i];

	int temp = N;
	sort(p + 1, p + N + 1, compA);
	for (int i = N; i > 0; i--) {
		if (p[i].distA == p[i - 1].distA) p[i].distA = temp;
		else p[i].distA = temp--;
	}
	temp = N;
	sort(p + 1, p + N + 1, compB);
	for (int i = N; i > 0; i--) {
		if (p[i].distB == p[i - 1].distB) p[i].distB = temp;
		else p[i].distB = temp--;
	}
	sort(p + 1, p + N + 1, compC);
	
	init(1, N, 1);
	
	queue<pair<int, int>> que;
	for (int i = 1; i <= N; i++) {
		if (p[i - 1].distC != p[i].distC) {
			while (!que.empty()) {
				update(1, N, que.front().first, que.front().second, 1);
				que.pop();
			}
		}
		int x = p[i].distA, y = p[i].distB;
		if (rangemin(1, N, 1, x - 1, 1) < y) continue;
		ans[p[i].idx] = 1;
		que.push({ x,y });
	}

	int Q; cin >> Q;
	while (Q--) {
		int x; cin >> x;
		if (ans[x]) cout << "YES\n";
		else cout << "NO\n";
	}
}