[BOJ 33531 // C++] Donor Time!

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 33531번 문제인 Donor Time!이다.
문제는 아래 링크를 확인하자.

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

 

1부터 \(N\)까지의 번호가 매겨진 정점과 해당 정점들을 잇는 \(S\)개의 양방향 에지가 있을 때 가장 가까운 Donor shop이 어디인지, 그리고 그 거리가 몇인지를 구하는 문제이다. 단, 가장 가까운 Donor Shop이 여럿 존재한다면 번호가 가장 작은 Donor Shop을 찾아야 한다.

 

1번 정점으로부터 다른 모든 정점까지의 최단거리는 dijkstra 알고리즘을 이용하여 한번에 모두 구할 수 있다. 따라서 이 문제는 dijkstra 알고리즘을 활용하는 것으로 쉽게 해결할 수 있다.

 

이 문제의 경우 모든 에지의 길이가 1 이상이므로, dijkstra 과정에서 방문하는 노드의 순서를 1번 정점으로부터 가장 가까운 순으로, 거리가 같다면 번호가 작은 순으로 어렵지 않게 뽑을 수 있어 조건을 만족하는 정점을 찾자마자 해당 답을 출력 후 프로그램을 중간에 종료시켜도 괜찮다.

 

아래는 제출한 소스코드이다.

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

int N, M;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
vector<pair<int, int>> G[10001];
bool donor[10001];
int dist[10001];
void dijkstra() {
    pq.push(make_pair(0, 1));
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    while (!pq.empty()) {
        int cur = pq.top().second, d = pq.top().first; pq.pop();
        if (dist[cur] < d) continue;
        if (donor[cur]) {
            cout << cur << ' ' << d;
            exit(0);
        }
        for (auto &p:G[cur]) {
            int nxt = p.first, dd = d + p.second;
            if (dd < dist[nxt]) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
        }
    }
}

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

    cin >> N >> M;
    while (M--) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }
    cin >> M;
    while (M--) {
        int x; cin >> x;
        donor[x] = 1;
    }
    dijkstra();
}