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

[문제]

18352번: 특정 거리의 도시 찾기 (acmicpc.net)

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

[문제 풀이]

다익스트라 알고리즘을 응용해서 쉽게 풀 수 있었던 문제.

다만, 기존의 간선의 값이 주어진 문제들과 달리 모두 1로 통일이었기에 다음에 더할값을 1로 통일만 시켰다.

[회고]

알고리즘은 모두 구현했으나 입력 코드를 구현 안하고 냈다가 틀렸다. 예시만 한번 돌려보면 바로 알 수 있는 부분이었는데 주의하자.

[코드]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define endl "\n"
#define INF 2000000000

using namespace std;

vector<int> graph[300001];

vector<int> dijkstra(int vertex, int start){
    vector<int> distance(vertex,INF);
    distance[start] = 0;    
    priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > pq;
    pq.push(make_pair(0,start));

    while(pq.size() > 0){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        if(distance[cur] < cost){
            continue;
        }

        for(int i = 0;i<graph[cur].size();i++){
            int next = graph[cur][i];
            int nCost = 1;

            if(distance[next] < nCost + cost){
                continue;
            }

            distance[next] = nCost + cost;
            pq.push(make_pair(nCost + cost,next));
        }
    }

    return distance;
}

int main(){
    int n,m,k,x;
    cin>>n>>m>>k>>x;
    n++;
    for(int i = 0;i<m;i++){
        int source,destination;
        cin>>source>>destination;
        graph[source].push_back(destination);
    }
    vector<int> answer = dijkstra(n,x);
    int count = 0;
    for(int i = 0;i<answer.size();i++){
        if(answer[i] == k){
            count++;
            cout<<i<<endl;
        }
    }
    if(count == 0){
        cout<<-1<<endl;
    }

    return 0;
}