[백준 18352] 특정 거리의 도시 찾기

문제 풀이

 

다익스트라의 기본 개념을 알고 있는지 묻는 문제다.

출발점 X의 도시에서 다른 모든 도시까지의 최단 경로를 구한 다음에

어떤 도시에서 출발해서 어떤 도시의 도착하는 비용이 K와 같다면 정답 배열에 넣고

정답 배열을 정렬해서 출력하면 된다.

만약에 배열의 사이즈가 0이라면 도시가 없기 때문에 -1을 출력하면 된다.

 

소스 코드

 

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

const int MAX = 300000 + 1;
const int INF = 987654321;
typedef pair<int, int> pii;

int N, M, K, X;
vector<pii> adj[MAX];

void dijkstra()
{
    vector<int> dist(N + 1, INF);
    priority_queue<pii> pq;
    pq.push({0, X});
    dist[X] = 0;
    while(!pq.empty())
    {
        int cur = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();
        
        if(dist[cur] < distance) continue;
        for(int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i].first;
            int nextDistance = adj[cur][i].second + distance;
            if(dist[next] > nextDistance)
            {
                dist[next] = nextDistance;
                pq.push({-nextDistance, next});
            }
        }
    }
    
    vector<int> ans;
    for(int i = 1; i <= N; i++)
    {
        if(dist[i] == K)
            ans.push_back(i);
    }
    
    if(ans.size() == 0)
        cout << "-1\n";
    else
    {
        sort(ans.begin(), ans.end());
        for(auto n : ans)
            cout << n << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> K >> X;
    for(int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b,1);
    }
    
    dijkstra();
    
    return 0;
}