동아리 활동 (JUNGOL 1994)

https://jungol.co.kr/problem/1994?cursor=NTA4LDAsOA==

---

아이디어

멀티소스 다익스트라를 이용해서 모든 노드에 대해 동아리로부터 떨어진 거리를 구해줍니다.

 

만약 하나의 시작점-도착점 쿼리가 있다면, 동아리로부터의 거리가 먼 노드부터 하나씩 추가하면서 시작점과 도착점이 연결되는 순간을 유니온 파인드를 이용해 구해주면 됩니다. 하지만 이러한 쿼리가 여러개가 있다면, PBS를 사용해야합니다. PBS는 병렬 이분 탐색으로, 어떤 쿼리에 대해서 동아리로부터의 거리가 가장 먼 K개의 노드만을 가지고 이동할 수 있는가? 라는 질문으로 매개변수탐색을 해주면 됩니다. 그러면 O(M log N)에 문제를 해결해줄 수 있습니다.

---

소스코드

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

vector <pair <int,int> > Graph[101010];
int MinDis[101010]={0};

void dij(int N,vector <int> Club)
{
    priority_queue <pair <int,int>, vector <pair <int,int> >, greater<> > pq;
    
    for (int i=1;i<=N;i++) MinDis[i]=2e9;

    for (int temp:Club)
    {
        MinDis[temp]=0;
        pq.push({0,temp});
    }

    while (pq.size())
    {
        auto [dis,now]=pq.top();
        pq.pop();
        
        if (MinDis[now]<dis) continue;

        for (auto [next,nextdis]:Graph[now])
        {
            if (MinDis[next]>nextdis+dis)
            {
                MinDis[next]=nextdis+dis;
                pq.push({nextdis+dis,next});
            }
        }
    }
}

int par[101010]={0};
int find(int x)
{
    if (x==par[x]) return x;
    return par[x]=find(par[x]);
}
void Union(int x,int y)
{
    par[find(x)]=find(y);
}
bool same(int x,int y)
{
    return find(x)==find(y);
}

int Ans[101010]={0}; //정답 인덱스
int s[101010]={0},e[101010]={0}; //PBS할때 쓰는 이분탐색 범위
int Start[101010]={0},End[101010]={0}; //시작노드, 도착노드

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N,M,K,Q,i,a,b,c;

    cin>>N>>M>>K>>Q;
    for (i=0;i<M;i++)
    {
        cin>>a>>b>>c;
        Graph[a].push_back({b,c});
        Graph[b].push_back({a,c});
    }

    vector <int> Club;
    for (i=0;i<K;i++)
    {
        cin>>a;
        Club.push_back(a);
    }

    dij(N,Club);
    vector <pair <int,int> > Node;
    for (int i=1;i<=N;i++) Node.push_back({MinDis[i],i});
    sort (Node.begin(),Node.end(),greater<>());

    for (i=1;i<=Q;i++)
    {
        cin>>Start[i]>>End[i];
        s[i]=0,e[i]=N-1;
    }

    vector <int> Neighboor[101010];
    for (i=1;i<=N;i++)
    {
        for (auto [next,nextdis]:Graph[i])
            if (MinDis[next]>=MinDis[i])
                Neighboor[i].push_back(next);
    }
    
    while (true)
    {
        vector <vector <int> > Mid(N);
        bool exist=false;

        for (i=1;i<=Q;i++)
        {
            if (s[i]<=e[i])
            {
                exist=true;
                Mid[(s[i]+e[i])/2].push_back(i);
            }
        }
        if (!exist) break;
        for (i=1;i<=N;i++) par[i]=i;

        for (i=0;i<N;i++)
        {
            for (auto next:Neighboor[Node[i].second])
                Union(next,Node[i].second);

            for (auto temp:Mid[i])
            {
                if (same(Start[temp],End[temp]))
                {
                    Ans[temp]=i;
                    e[temp]=i-1;
                }
                else s[temp]=i+1;
            }
        }
    }

    for (i=1;i<=Q;i++)
        cout<<Node[Ans[i]].first<<"\n";
}