※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 2472번 문제인 체인점이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/2472
2472번: 체인점
첫째 줄에는 매장 후보지의 개수를 나타내는 정수 N이 입력된다(1 ≤ N ≤ 100,000). 매장 후보지들은 1부터 N까지의 번호로 구분된다. 둘째 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수 A, B,
www.acmicpc.net
각 장소에서 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";
}
}728x90
'BOJ' 카테고리의 다른 글
| [BOJ 9466 // C++] 텀 프로젝트 (0) | 2021.09.27 |
|---|---|
| [BOJ 17609 // C++] 회문 (0) | 2021.09.26 |
| [BOJ 1615 // C++] 교차개수세기 (0) | 2021.09.24 |
| [BOJ 1017 // C++] 소수 쌍 (0) | 2021.09.23 |
| [BOJ 10282 // C++] 해킹 (0) | 2021.09.22 |