BOJ 2472 - 체인점 (다익스트라, 좌표압축, 세그트리, 수학)

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

이런 문제 3문제를 3시간안에 중학생이 푼다

 

<문제설명>

최대 n개의 정점으로 이뤄진 무방향 가중치 그래프가 주어진다. (n<=1e5, 한 정점당 최대 5개의 간선이 있다.) 

 

정점i에서 a,b,c점까지 떨어진 거리를 {xi, yi, zi}라고 하자. 어떤 i,j에 대해 xi<xj, yi<yj, zi<zj인 j정점은 NO, 나머지는 YES를 출력하자.

 

<풀이>

a,b,c에서 모든 정점으로의 최단경로를 기준으로 {x,y,z,id}를 만든 후엔 이전 포스팅(굉장한 학생)과 풀이가 유사하다.

 

최단경로가 1e9에 근접하는 경우가 생기고 그 종류는 한정(대충3e5)되어 있으므로 {x,y,z,id}엔 경로압축한 값을 넣어준다.

 

x값이 중복될 수 있으므로, https://www.acmicpc.net/board/view/50251 와 같은 경우가 생길 수 있다.

 

x기준 정렬후 수행, y기준 정렬후 수행, z기준 정렬 후 수행한 후에

chk[i][0] && chk[i][1] && chk[i][2]인 경우 NO를 뽑아준다.

 

 

<코드>

typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;
const int MAX = 1e5 + 4;
const int SMAX = (1 << 18);
const int INF = 0x3f3f3f3f;

int n, m, seg[SMAX], st[3], d[3][MAX];
vector<P> g[MAX];
T dist[MAX];
bool vst[MAX], chk[MAX][3];

void update(int i, int x) {
	i += SMAX / 2;
	seg[i] = min(seg[i], x);
	while (i > 1) {
		i /= 2;
		seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
	}
}

int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return INF;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return min(val(s, e, node * 2, ns, mid), val(s, e, node * 2 + 1, mid + 1, ne));
}
int val(int s, int e) { return val(s, e, 1, 0, SMAX / 2 - 1); }


void maked(int i) { //st[i]~모든 지점까지의 거리
	memset(vst, 0, sizeof(vst));
	priority_queue<P, vector<P>, greater<P>> pq;
	d[i][st[i]] = 0;
	pq.push({ d[i][st[i]], st[i] });

	while (!pq.empty()) {
		int u = pq.top().second; pq.pop();
		if (vst[u]) continue;
		vst[u] = true;
		for (P p : g[u]) {
			int v, w; tie(v, w) = p;
			if (d[i][v] > d[i][u] + w) {
				d[i][v] = d[i][u] + w;
				pq.push({ d[i][v], v });
			}
		}
	}

	vector<int> s;
	for (int j = 1; j <= n; j++) s.push_back(d[i][j]);
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	for (int j = 1; j <= n; j++)
		d[i][j] = lower_bound(s.begin(), s.end(), d[i][j]) - s.begin();
}

int main() {
	FAST; cin >> n;
	for (int i = 0; i < 3; i++) cin >> st[i];
	cin >> m;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
	}

	memset(d, 0x3f, sizeof(d));
	for (int i = 0; i < 3; i++) maked(i);

	for (int i = 1; i <= n; i++) {
		get<0>(dist[i]) = d[0][i];
		get<1>(dist[i]) = d[1][i];
		get<2>(dist[i]) = d[2][i];
		get<3>(dist[i]) = i;
	}
	
	sort(dist + 1, dist + n + 1);
	memset(seg, 0x3f, sizeof(seg));
	for (int i = 1,x,y,z,id; i <= n; i++) {
		tie(x, y, z, id) = dist[i];
		
		if (y>0 && val(0, y - 1) < z) chk[id][0] = 1;
			
		update(y, z);
	}

	sort(dist + 1, dist + n + 1, [] (T t1, T t2) {
		return get<1>(t1) < get<1>(t2);
	});
	memset(seg, 0x3f, sizeof(seg));
	for (int i = 1, x, y, z, id; i <= n; i++) {
		tie(x, y, z, id) = dist[i];

		if (x > 0 && val(0, x - 1) < z) chk[id][1] = 1;

		update(x, z);
	}

	sort(dist + 1, dist + n + 1, [](T t1, T t2) {
		return get<2>(t1) < get<2>(t2);
		});
	memset(seg, 0x3f, sizeof(seg));
	for (int i = 1, x, y, z, id; i <= n; i++) {
		tie(x, y, z, id) = dist[i];

		if (x > 0 && val(0, x - 1) < y) chk[id][2] = 1;

		update(x, y);
	}


	int query; cin >> query;
	while (query--) {
		int i; cin >> i;
		cout << (chk[i][0] && chk[i][1] && chk[i][2] ? "NO\n" : "YES\n");
	}
}

 

<생각>

글을 쓰는 시점에선 중복되는 값을 고려하지 않은 풀이도 맞게 채점된다. 테스트케이스 추가 요청해둠