Baekjoon 18352번 특정 도시의 거리 찾기

문제

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

걸린 시간

00 : 26 : 57

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m, k, x;
vector<int> result;
vector<int> dist(300001, INF);
vector<pair<int, int>> adj[300001]; // vertex, cost

void dijkstra(int src){
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(src, 0));
    dist[src] = 0;
    while(!pq.empty()){
        int here = pq.top().first;
        int cost = -pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            if(nextDist < dist[there]){
                dist[there] = nextDist;
                pq.push(make_pair(there, -nextDist));
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k >> x;
    int a, b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a].push_back(make_pair(b, 1));
    }
    dijkstra(x);
    for(int i = 1; i <= n; i++)
        if(dist[i] == k)
            result.push_back(i);
    if(result.size() != 0)
        for(int i = 0; i < result.size(); i++)
            cout << result[i] << "\n";
    else
        cout << "-1\n";
    return 0;
}