[백준] 17835번 면접보는 승범이네 (C++)

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

 

 

이 문제는 N개의 노드와 M개의 양방향 간선이 주어지고 K개의 면접장의 수가 주어진다.

 

이때 K 노드를 제외한 모든 노드에서 K개의 노드에 최단거리중 가장 먼 거리와 노드를 찾는 문제이다.

 

노드의 개수와 간선의 개수는 최대 10만과 50만으로 다익스트라를 K번 최대 10만번 수행하기에는 시간초과가 난다.

O(N * N log M)

 

그렇다면 O(N log M) 한번으로 풀 수는 없을까??

 

생각을 다르게 해봐서 K개의 노드를 시작점으로 잡고 해당 노드를 제외한 모든 노드의 최단 거리를 알 수 있다.

 

시작점(N개 노드) -> 도착점(K개 노드)

 

이 문제를

 

시작점(K개 노드) -> 도착점(N개 노드)

로 변화하여 풀 수 있다는 말이다.

 

따라서 K개의 노드를 우선순위 큐에 넣고 다익스트라를 한번만 사용하여 최단거리 중 가장 먼 거리의 노드와 거리를 찾고

출력하면 해결되는 문제이다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e11

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M, K;
vector<vector<pii>> v(100001);
ll dist[100001];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

void dijkstra() {
    while(!pq.empty()) {
        int Node = pq.top().second;
        ll cost = pq.top().first;
        pq.pop();

        if(dist[Node] < cost) continue;

        for(auto it : v[Node]) {
            int nextNode = it.first;
            ll nextCost = cost + it.second;

            if(dist[nextNode] > nextCost) {
                pq.push({nextCost, nextNode});
                dist[nextNode] = nextCost;
            }
        }
    }
}

void solve() {
    dijkstra();

    int maxNode = 0;
    ll maxDist = 0;

    for(int i = 1; i <= N; i++) {
        if(dist[i] > maxDist) {
            maxNode = i;
            maxDist = dist[i];
        }
    }

    cout << maxNode << "\n" << maxDist;
}

void input() {
    cin >> N >> M >> K;

    fill(dist, dist+N+1, MAX);

    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[b].push_back({a, c});
    }

    for(int i = 0; i < K; i++) {
        int a;
        cin >> a;
        pq.push({0, a});
        dist[a] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}