백준 16211번 백채원

백준 16211번 백채원

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>    
using namespace std;
#define MAX 200010
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF =321321321321;
vector<pll > adj[MAX];
ll dist[MAX+100];
ll dist2[MAX + 100];
bool visited[MAX];
ll N, M,K;
void dijkstra(int start) {
    fill(dist, dist + MAX + 1, INF);
    priority_queue<pll, vector<pll >, greater<pll> > pq;
    pq.push({ start,0 });
    dist[start] = 0;
    while (!pq.empty()) {
        ll here = pq.top().first;
        ll cost = pq.top().second;
        pq.pop();
        if (dist[here] != cost)continue;
        for (pll &p : adj[here]) {
            ll there = p.first;
            ll new_cost = cost + p.second;
            if (dist[there] > new_cost) {
                dist[there] = new_cost;
                pq.push({ there, new_cost });
            }
        }
    }
}
void dijkstra2(vector<ll> arr) { //백채원을 잡는 추종자들 위치를 한꺼번에
                                 //다익스트라로 돌려주면
                                 //dist2[i]에는 우선순위큐에들어간 모든 추종자들중에 i정점에
                                 //제일 가까운추종자의 거리가 들어간다.
    fill(dist2, dist2 + MAX + 1, INF);
    priority_queue<pll, vector<pll >, greater<pll> > pq;
    for (int i = 0; i < arr.size(); i++) {
        pq.push({ arr[i],0 });
        dist2[arr[i]] = 0;
    }
    while (!pq.empty()) {
        ll here = pq.top().first;
        ll cost = pq.top().second;
        pq.pop();
        if (dist2[here] != cost)continue;
        for (pll &p : adj[here]) {
            ll there = p.first;
            ll new_cost = cost + p.second;
            if (dist2[there] > new_cost) {
                dist2[there] = new_cost;
                pq.push({ there, new_cost });
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    vector<ll> arr;    //백채원을 잡으려는 추종자 위치 벡터
    for (int i = 0; i < K; i++) {
        int a;
        cin >> a;
        arr.push_back(a);
    }
    dijkstra(1);
    dijkstra2(arr);
    priority_queue<int, vector<int >, greater<int> > pq;
    for (int i = 2; i <= N; i++) {
        if (dist[i] < dist2[i]) //모든 추종자들보다 백채원이 집에 더 가까운 경우!
            pq.push(i);
    }
    if (pq.empty()) {
        cout << 0;
        return 0;
    }
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
 
    return 0;
}

출처:https://www.acmicpc.net/problem/16211

MAX값을 2백만으로 잡고 푸니까 배열이 터졌는데 계속 어디가 문제인지 못찾아서 틀렸습니다를 받았네요 ㅋㅋ

이 문제를 풀 때 제일 일반적으로 생각하는 방법은

다익스트라를 추종자들 입장에서 모두 돌려보는 것입니다. 

그러나 이렇게 풀게 되면 시간복잡도에서 문제가 터집니다.

1.이 문제를 해결하기 위해서는 추종자들의 모든 위치를 우선순위큐에 넣고 한꺼번에 다익스트라를 실행하는 것입니다.

이렇게 하면 dist2[i]는 모든 추종자들중에 i번 정점에 가까운 거리가 저장되게 됩니다.

왜 이렇게 되는 건지 설명을 하자면 모든 추종자들과의 거리가 0인 가상의 점이 있다고 가정하고,

다익스트라를 돌렸을 때를 생각해보시면 됩니다. 그 가상의 점을 기준으로 다익스트라를 돌렸을 때, 위의 설명과 같은 

결과가 나오게 되는 것을 확인 하실 수 있습니다.