[BOJ] 백준 16211 백채원

문제 링크

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

 

다익스트라를 이용해서 풀 수 있는 문제입니다.

1) 백채원이 1번 지점에서 출발해 다른 모든 지점으로 가는 최단 거리(시간)를 구합니다.

2) 추종자 K명이 임의의 K개 지점에서 출발해 다른 모든 지점으로 가는 최단 거리를 구합니다.

3) 1번 지점을 제외한 모든 지점에 대해, 백채원이 추종자들보다 더 빠르게 도착할 수 있다면 정답에 추가합니다.

 

 

이 문제를 검색하시는 분들은 대부분 2)에서 막혀서 검색해보셨을 거에요.

생각보다 간단합니다. 다익스트라를 돌릴 때 K개 지점을 모두 큐에 넣고 시작하면 됩니다.

 

다익스트라의 원리가 현재까지 최단 거리임이 보장된 정점들의 코스트를 기반으로 아직 보장되지 않은 정점 중 코스트가 가장 작은 정점을 확장해나가는 방식입니다. 따라서 시작점 여러 개를 한 번에 큐에 넣어도 상관없습니다. 시작점들의 코스트를 0으로 초기화해주면 어떤 정점에서 출발했는지는 알 수 없지만, 적어도 그 시작점 중에서 가장 빠르게 특정 지점으로 갈 수 있는 거리가 구해지게 됩니다.

 

 

 

 

 

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
 
struct Node {
    int to, cost;
};
int n, m, k;
vector<int> d1, d2;
vector<vector<Node>> p;
vector<int> dijkstra(vector<int> st) {
    priority_queue<pair<int, int>> q;
    vector<int> dist(2 * n, INF);
    vector<bool> chk(2 * n);
 
    for (int x : st)q.push({ 0, x }), dist[x] = 0;
 
    while (!q.empty()) {
        int now = q.top().second;
        q.pop();
        if (chk[now]) continue;
        chk[now] = true;
 
        for (auto e : p[now]) {
            int next = e.to;
            int ncost = e.cost;
            if (dist[next] > dist[now] + ncost) {
                dist[next] = dist[now] + ncost;
                q.push({ -dist[next], next });
            }
        }
    }
    return dist;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> k;
    p.resize(n * 2);
    for (int i = 0; i < m; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        p[x].push_back({ y, t });
        p[y].push_back({ x, t });
    }
    vector<int> temp;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        temp.push_back(x);
    }
    d1 = dijkstra(vector<int>(1, 1));
    d2 = dijkstra(temp);
    vector<int> ans;
    for (int i = 2; i < n + 1; i++) {
        if (d1[i] < d2[i]) {
            ans.push_back(i);
        }
    }
    if (ans.empty()) cout << 0;
    else for (int x : ans)cout << x << ' ';
}