글 읽기 - 2472 체인점문제 질문

whquddn55 6년 전 0

1. 다익스트라로 a, b, c에서의 모든 정점까지의 최소거리 저장

2. a에서의 최소거리를 기준으로 정렬

3. 정렬된 정점을 순서대로 돌며 segment tree에 갱신하는 작업을 수행

segment tree의 index는 b까지의 거리를, 원소는 c까지의 거리의 최소 값을 저장. 즉, 각 정점을 돌 때마다 tree[b까지의 거리]에 (c까지의 거리)를 갱신 해주고, tree[0, b까지의 거리 - 1]의 최소값과 (c까지의 거리)를 비교하여 최솟값이 더 작으면 false로, 아니면 true로 하여 저장 -> 출력

런타임에러가 뜨는것으로 보아 (b까지의 거리)의 최대값을 n으로 넘겨 tree의 크기를 사이징해주다보니 INT_MAX만큼 사이징되면 약 2기가바이트... 먹더라구요. 그래서 여러가지 테스트 많이 해봤는데

1. INT_MAX만큼 사이징하면 런타임에러가 아니라 메모리초과로 뜨는데 그럼...

2. 정올에 넣으니 런타임에러뜰 뿐만 아니라 틀린 TC도 여러개 보입니다. 대충 보니 YES로 나와야할 값들은 YES로 잘 나오는데 NO로 나와야하는 값들은 몇몇개가 YES로 나옵니다. 즉, true로 체크됩니다.

굉장한학생

이 문제도 정확히 동일한 알고리즘으로 풀었는데 이 문제랑 다르게 중복되는 값이 있어서 그런가 통과를 못 하네요.. 아래는 굉장한 학생 풀면서 메모한거 긁어온겁니다.

첫번째 등수를 기준으로 정렬
세그먼트트리 구성 ((0 ~ 두번째등수 - 1)사이의 c의 최소값을 구성하는)
최소값이 있다? -> 두번째 등수가 높은(숫자가 낮은) 학생이 있다.
최소값이 세번째 등수보다 작다? -> 세번째 등수가 높은(숫자가 낮은) 학생이 있다.
첫번째 등수는 정렬했으므로 숫자가 낮은 학생이 항상있으므로 세 숫자가 모든 낮은 학생이 존재하게되며 게임 끝났따

뭐가 문제일까요?

#include <bits/stdc++.h>
using namespace std;
#define INF (INT_MAX / 2)
typedef pair<int, int> pii;

struct Dist {
	int a = INF, b = INF, c = INF;
	int index;

	bool operator<(const Dist& other) {
		return (a == other.a) ? ((b == other.b) ? (c < other.c) : (b < other.b)) : (a < other.a);
	}
};

int n;
int a, b, c;
int m;
vector<Dist> dists;
vector<vector<pii> > adj;
vector<bool> canPlace;

struct SegmentTree {
	vector<int> tree;
	SegmentTree(int n)
		:tree(1 << (int)(ceil(log2(n)) + 1), INT_MAX) { }

	int pQuery(int node, int nodeLeft, int nodeRight, int left, int right) {
		if (right < nodeLeft || left > nodeRight)
			return INT_MAX;
		if (left <= nodeLeft && nodeRight <= right)
			return tree[node];

		return min(pQuery(node * 2, nodeLeft, (nodeLeft + nodeRight) / 2, left, right),
			pQuery(node * 2 + 1, (nodeLeft + nodeRight) / 2 + 1, nodeRight, left, right));
	}
	int pUpdate(int node, int nodeLeft, int nodeRight, int index, int newValue) {
		if (index < nodeLeft || index > nodeRight)
			return tree[node];
		if (nodeLeft == nodeRight)
			return tree[node] = min(tree[node], newValue);

		return tree[node] = min(pUpdate(node * 2, nodeLeft, (nodeLeft + nodeRight) / 2, index, newValue),
			pUpdate(node * 2 + 1, (nodeLeft + nodeRight) / 2 + 1, nodeRight, index, newValue));
	}
	
	int query(int left, int right) {
		return pQuery(1, 0, n - 1, left, right);
	}
	int update(int index, int newValue) {
		return pUpdate(1, 0, n - 1, index, newValue);
	}
};

void dijkstra() {
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	pq.emplace(0, a);
	dists[a].a = 0;
	
	while (!pq.empty()) {
		int cost = pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if (dists[here].a < cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i].first;
			int nextDist = adj[here][i].second + cost;

			if (nextDist < dists[next].a) {
				dists[next].a = nextDist;
				pq.emplace(nextDist, next);
			}
		}
	}
	
	pq.emplace(0, b);
	dists[b].b = 0;

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

		if (dists[here].b < cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i].first;
			int nextDist = adj[here][i].second + cost;

			if (nextDist < dists[next].b) {
				dists[next].b = nextDist;
				pq.emplace(nextDist, next);
			}
		}
	}

	pq.emplace(0, c);
	dists[c].c = 0;

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

		if (dists[here].c < cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i].first;
			int nextDist = adj[here][i].second + cost;

			if (nextDist < dists[next].c) {
				dists[next].c = nextDist;
				pq.emplace(nextDist, next);
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	scanf("%d %d %d", &a, &b, &c);
	scanf("%d", &m);
	a--;
	b--;
	c--;

	adj.resize(n);
	while (m--) {
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		from--;
		to--;
		adj[from].emplace_back(to, cost);
		adj[to].emplace_back(from, cost);
	}
	dists.resize(n);
	for (int i = 0; i < n; i++)
		dists[i].index = i;
	dijkstra();
	sort(dists.begin(), dists.end());

	int maxValue = 0;
	for (int i = 0; i < n; i++) {
		maxValue = max(maxValue, dists[i].b);
	}

	SegmentTree stree(maxValue);
	canPlace.resize(n, false);
	for (int i = 0; i < n; i++) {
		stree.update(dists[i].b, dists[i].c);
		if (dists[i].c > stree.query(0, dists[i].b - 1))
			continue;
		canPlace[dists[i].index] = true;
	}
	
	int t;
	scanf("%d", &t);
	while (t--) {
		int q;
		scanf("%d", &q);
		printf("%s\n", canPlace[q - 1] ? "YES" :"NO");
	}

	return 0;
}