[도전 8일차] 체인점 - KOI 고등부 2번

※복습 : 

문제 : BOJ 2472 체인점

KOI 2010 고등부 2번 체인점

문제 링크

 

사용 알고리즘 : 다익스트라, 세그먼트 트리

 

 

문제 요약 :

N (<=10^5) 개의 매장 후보지 1~N이 있다. 그 중 3개는 아파트 단지이며, 중요하므로 A,B,C라 부르자.

이제 n개의 매장 후보지를 가지고 가중치 그래프를 구성한다. 이때 각 매장 후보지에서 연결된 다른 후보지의 개수는

5개 이하이며, 한 후보지에서 다른 임의의 후보지로 가는 경로가 항상 존재한다. 

 

매장 후보지를 매장으로 선정하는 조건은 다음과 같다.

 매장 후보지 p에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 a, b, c라고 하고 다른 매장 후보지 q가 존재해서 q에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 x, y, z라고 할 때, a > x 이고 b > y 이고 c > z이면 p에는 매장을 설치하지 않는다.

 

M개의 후보지 번호가 입력으로 주어질 때, 각각의 후보지가 매장이 될 수 있을 지 YES / NO 로 구분해 출력하는 것이 목표다.

풀이:

중요한 것은 후보지로부터 아파트까지의 거리이므로 반대로 생각하면 아파트부터 후보지까지의 거리이다.

가중치 그래프에서 최단경로를 구하는 것이므로 아파트 3군데에서 다익스트라 알고리즘을 사용하자.

정점의 수 V<=10^5이고 , 간선의 수 E<= N*5 /2 <= 25 * 10^5 를 만족하므로 O(E log V)의 시간복잡도를 가지는

다익스트라 알고리즘을 사용할 수 있다.

 

후보지 p가 후보지 q 보다 모든 아파트까지의 거리가 작으면 p가 q를 포함한다고 하자.

각 후보지로부터 아파트까지의 거리를 구했으므로

어떤 후보지에도 포함되지 않는 후보지를 구해주면 된다. (이 후보지는 매장이 될 수 없다.)

 

방법은 다음과 같다.

매장 후보지 p에서 아파트 단지 A, B, C까지의 최단 경로 길이를 각각 a, b, c라 하자.

 

1. 후보지들을 a가 작은 순서대로, a가 같다면 b,c순으로 큰 순서대로 정렬한다. 

 

-후보지들을 정렬된 순서대로 살펴본다면 어떤 후보지 p가 포함될 수 있는 후보지는 p 이전에 살펴본 후보지일 것이다. 

 

2. b의 값을 원소로 하는 배열을 만든 다음, b의 값을 기준으로 얼마나 작은지 각 후보지의 순위 (1~n)을 구해준다.

 

3. 2번에서 구한 순위를 인덱스 (idx)로 하면서 그에 대응하는 c의 값을 원소로 하는 최솟값 트리를 만들 것이다. 이때 IDT, Segment Tree, BIT 로 구현이 가능하다.  한번 살펴볼 때 1~idx-1 범위 내에서 c의 최솟값을 구해준다.  만약 그 최솟값이 현재 살펴보고 있는 c보다 크거나 같다면 후보지 p는 어떤 후보지에도 포함되지 않는다. 

 

다시 한 번 강조하지만 현재 살펴보고 있는 a,b,c에 대해

앞서 살펴본 p,q,r 중 p<a, q<b, r<c인 경우가 있었는지 판정하는 것이 목표다.

 

*a의 값 또는 idx가 같은 경우가 존재할 수 있다.

i) a가 같은 후보지들끼리 포함될 수 없으므로, b,c가 큰 순으로 정렬하여 항상 idx가 큰 순부터 업데이트 되도록 했다. (어차피 1~idx-1 사이만 살펴보므로 idx가 큰 것부터 살펴본다면 a가 같은 후보지들끼리는 서로의 판단에 영향을 주지 않는다.)

 

ii) b가 서로 같은 경우 같은 idx를 가진다. 이때 세그먼트 트리의 일반적인 업데이트와 다르게, 노드에 들어온 값과 새로 들어온 값 중 최솟값으로 업데이트를 수행하자. 그렇게 하면 앞서 있었던 정보를 유지할 수 있다.

그렇게 n개의 후보지에 대한 판단을 bool 배열에 저장하여 답을 출력하자.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const ll INF = 1e15;
using namespace std;
int n,m,t,q,D[3];
bool ans[100001];
ll d[3][100010];
struct node{
    int x;
    ll w;
    bool operator< (const node&tmp) const{
        return w>tmp.w;
    }
};
vector<node> v[100010];
void Dijkstra(int s,ll dis[]){
    priority_queue<node> pq;
    fill(dis,dis+n+1,INF);
    pq.push({s,0}); dis[s]=0;
    while(!pq.empty()){
        node cur=pq.top(); pq.pop();
        int x=cur.x; ll dist=cur.w;
        if(dist>dis[x]) 
            continue;
        for(node& next : v[x]){
            int a=next.x,w=next.w;
            if(dis[a]>dist+w){
                dis[a]=dist+w;
                pq.push({a,dis[a]});
            }
        }
    }
}
vector<int> Q;
bool cmp(const int& q1,const int& q2){
    if(d[0][q1]==d[0][q2]){
        if(d[1][q1]==d[1][q2])
            return d[2][q1]>d[2][q2];
        return d[1][q1]>d[1][q2];
    }
    return d[0][q1]<d[0][q2];
}
struct IDT{
    int base;
    vector<ll> tree;
    IDT(int n){
        for(base=1;base<n;base<<=1);
        tree = vector<ll>(base<<1,INF);
    }
    void update(int pos,ll val){
        pos+=base;
        tree[pos]=min(tree[pos],val);
        while(pos>>1){
            tree[pos>>1] = min(tree[pos],tree[pos^1]);
            pos>>=1;
        }
    }
    ll get_min(int l,int r){
        l+=base; r+=base;
        ll res=INF;
        while(l<r){
            if(l&1) res=min(res,tree[l++]);
            if(!(r&1)) res=min(res,tree[r--]);
            r>>=1; l>>=1;
        }
        if(l==r)
            res=min(res,tree[l]);
        return res;
    }
};
vector<ll> B;
inline int get_idx(ll x){
    return lower_bound(B.begin(),B.end(),x)-B.begin();
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=0;i<3;i++)
        cin>>D[i];
    cin>>m;
    for(int i=0,a,b,w;i<m;i++){
        cin>>a>>b>>w;
        v[a].push_back((node){b,w});
        v[b].push_back((node){a,w});
    }
    for(int i=0;i<3;i++)
        Dijkstra(D[i],d[i]);
    for(int i=1;i<=n;i++){
        Q.push_back(i);
        B.push_back(d[1][i]);
    }
    vsort(B);
    sort(Q.begin(),Q.end(),cmp);
    B.erase(unique(B.begin(),B.end()),B.end());
    IDT C(n);
    for(int i=0;i<n;i++){
        q=Q[i]; int idx=get_idx(d[1][q]);
        if(C.get_min(0,idx-1)>=d[2][q])
            ans[q]=true;
        C.update(idx,d[2][q]);
    }
    cin>>t;
    while(t--){
        cin>>q;
        cout<<(ans[q]?"YES\n":"NO\n");
    }
}