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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net



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

bool visited[300001];
pair <int, int> edge[1000001];

int main () {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    priority_queue <int,vector<int>,greater<int>> q;
   
    int N,M,K,X,dist = 0; // 도시 , 도로, 거리, 출발 도시
   
    cin >> N >> M >> K >> X;

    for ( int i = 0 ; i < M; i++) {
        cin >> edge[i].first >> edge[i].second ;
        if ( edge[i].first == X) {
            q.push(edge[i].second); // 출발점에서 거리가 1인 도시
            visited[edge[i].second] = true; // 방문했음을 체크
            dist = 1; // 현재까지 거리 = 1
        }
           
    }

    visited[X] = true; // 출발점은 거리가 0 이고, X 는 0 이 될 수 없으므로 방문체크
    sort(edge, edge+M);

    while(1) {
        if ( dist == K) // 최단거리(dist) 가 K가 되면 break
            break;
        priority_queue <int,vector<int>,greater<int>> pq;
        while(!q.empty()) { // 출발점에서 최단거리 = dist 인 도시를 꺼내면서  dist+1 인 도시들을 pq에 저장
            int temp = q.top(); // temp = 거리가 dist 인 도시
            q.pop();
            visited[temp] = true;
            for ( int i = 0 ; i < M;i++) {
                if ( edge[i].first > temp) // edge 는 정렬되어 있으므로, 출발점보다 큰 도시를 체크하는 순간 break
                    break;
                if ( edge[i].first == temp && !visited[edge[i].second]) { // 방문한 적이 없는 도시이면서, 출발점이 temp 라면
                    visited[edge[i].second] = true;  
                    pq.push(edge[i].second); // 도착점을 저장
                }
            }
        }
        dist++; // 거리 증가
        q = pq;
    }

    int qs = q.size();

    if ( qs == 0) { //
        cout << -1;
        return 0;
    }

    for ( int i = 0 ; i < qs; i++) {
        cout << q.top() << "\n";
        q.pop();
    }



   
}


풀다보니까 굳이 우선순위 큐로 안해도 될거 같긴 했는데 바꾸기 귀찮아서..

시간초과 나면 바꿔야겠단 마인드로 일단 제출했는데  75%에서 실패했습니다 뜨네.. 75%까지 맞은거 보면 완전 잘못 접근한거 같지는 않은데 

왜 틀린지 모르겠음..ㅠㅠ