안녕하세요. WHITECOLLAR를 풀고 있습니다.
풀이 알고리즘은 다음과 같은데, 뭐가 오류인지 안풀리네요.

1) 0 -> N-1 으로 가는 경로를 BFS를 통해 찾습니다.
2) 실제 경로를 구합니다.
여기서, 실제 경로가 나오지 않는 경우는 100만개짜리 크기의 vector를 반환합니다.
3) 지금까지 찾은 최소 경로보다 더 짧은 경로를 찾은 경우, 지금까지 체크한 답 (map)을 없애버립니다.
4) 최소 경로보다 같거나 작은 값을 찾은경우 최소 경로의 크기를 갱신합니다.
5) 100만개 크기의 vector가 return 된 경우, 무한반복문을 종료하고 답을 출력하는 루틴으로 넘어갑니다.
6) map를 이용해, 답이 될수 있는값을 map에 체크합니다.
7) 지금 이용한 간선을 끊어버립니다.

8) 5)에서 넘어온경우 출력합니다.

논리적 문제가 있는지, 코딩에 문제가 있는지 잘 모르겠네요 ㅜㅜ

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
#define INF 987654321
using namespace std;
void bfs(int src, vector<vector<int> >& graph, vector<int>& parent){
    int N = graph.size();
    vector<int> visit = vector<int>(N, 0);
    parent= vector<int>(N, -1);
    queue<int> q;
    visit[src] = 1;
    parent[src] = src;
    q.push(src);
    while (!q.empty()){
        src = q.front();
        q.pop();
        for (int i = 0; i < N; i++){
            if (graph[src][i] == 1 && !visit[i]){
                visit[i] = 1;
                parent[i] = src;
                q.push(i);
            }
        }
    }
}

vector<int> solve(int v, const vector<int>& parent){
    vector<int> mang(1000000, 0);
    if (v == -1){ return mang; }
    vector<int> path(1, v);
    while (parent[v] != v){
        v = parent[v];
        if (v == -1){ return mang; }
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}
int main(){
    double C;
    cin >> C;
    while (C--){
        int N, M;
        cin >> N >> M;
        vector<vector<int > > graph;
        for (int i = 0; i < N; i++){ 
            vector<int> vbuf;
            for (int j = 0; j < N; j++){
                vbuf.push_back(0);
            }
            graph.push_back(vbuf);
        }

        for (int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            a--; b--;
            graph[a][b] = 1;
        }
        int smallsize = INF;
        map<int, int> lastret;
        while (true){
            vector<int> parent;
            parent.clear();
            bfs(0, graph, parent);
            vector<int> ret = solve(N - 1, parent);
            if (smallsize>ret.size()){
                lastret.clear();
            }
            if (smallsize >= ret.size()){ smallsize = ret.size(); }
            if (ret.size() == 1000000){ break; }
            for (int i = 0; i < ret.size(); i++){
                lastret[ret[i]] = 1;
            }
            for (int i = 0; i < ret.size() - 1; i++){
                int a = ret[i];
                int b = ret[i + 1];
                graph[a][b] = 0;
            }
        }
        map<int, int>::iterator it;
        vector<int> finalret;
        for (it = lastret.begin(); it != lastret.end(); it++){
            finalret.push_back(it->first + 1);
        }
        for (int i = 0; i < finalret.size() - 1; i++){
            cout << finalret[i] << " ";
        }
        cout << finalret[finalret.size() - 1] << endl;
        
    
    }
    system("pause");
}