问题：为什么用deque反向输出会报错而用递归反向输出没问题

Question

http://poj.org/problem?id=2457
（由于题目是英文，以下图片时中文翻译后的图片）
https://img-mid.csdnimg.cn/release/static/image/mid/ask/800335390746158.png?x-oss-process=image/auto-orient,1
https://img-mid.csdnimg.cn/release/static/image/mid/ask/394075390746180.png?x-oss-process=image/auto-orient,1

（由于题目是英文，以下图片时中文翻译后的图片）

#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
#include<deque>
using namespace std;
const int  N=1e5+10,M=2e5+10;
typedef pair<int,int> PII;
int dis[N],k,head[N],n,idx,m,s=1,t,vis0[N];
bool vis[N];
struct Edge{
    int to,w,next;
}edge[M];
void add(int a,int b ,int c)
{
    edge[idx].to=b,edge[idx].w=c,edge[idx].next=head[a],head[a]=idx++;
}
void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=1;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({1,s});
//    vis0[1]=1;
    while(heap.size())
    {
        int vertax = heap.top().second;
        heap.pop();
        
        if(vis[vertax])continue;
        vis[vertax]=true;
//        cout<<vertax<<" ";
        for(int i = head[vertax]; i != -1; i = edge[i].next)
        {
            int j=edge[i].to;
            if(dis[j]>dis[vertax]+edge[i].w)
            {
                dis[j]=dis[vertax]+edge[i].w;
                vis0[j]=vertax;
                heap.push({dis[j],j});
            }
        }
        
    }
}
deque<int> stars;
void print_stars()
{
 
    
    stars.push_front(n);
    k=n;
    while(vis0[k]!=s)
    {
        k=vis0[k]; 
        stars.push_front(k);
    }
    stars.push_front(s);
}
int main()
{
    int a,b,c;
    memset(head,-1,sizeof head);
    cin>>m>>n;
//    if(n==1)
//    {
//        cout<<"1"<<'\n'<<"1"<<'\n';
//    }
//    else{
    
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            c=1;
            add(a,b,c);
//            add(b,a,c);
        }
        dijkstra();
        if(dis[n]==0x3f3f3f3f)
        {
            cout<<"-1";
        }
        else{
            cout<<dis[n]<<'\n';
            print_stars();
            while(stars.size())
            {
                cout<<stars.front()<<'\n';
                stars.pop_front();
            }
//        }
    }
    return 0;
}
 

（以下时将deque该换成递归之后可以通过的代码）

 
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
#include<deque>
using namespace std;
const int  N=1e5+10,M=2e5+10;
typedef pair<int,int> PII;
int dis[N],k,head[N],n,idx,m,s=1,t,vis0[N];
bool vis[N];
struct Edge{
    int to,w,next;
}edge[M];
void add(int a,int b ,int c)
{
    edge[idx].to=b,edge[idx].w=c,edge[idx].next=head[a],head[a]=idx++;
}
void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,s});
//    vis0[1]=1;
    while(heap.size())
    {
        int vertax = heap.top().second;
        heap.pop();
        
        if(vis[vertax])continue;
        vis[vertax]=true;
//        cout<<vertax<<" ";
        for(int i = head[vertax]; i != -1; i = edge[i].next)
        {
            int j=edge[i].to;
            if(dis[j]>dis[vertax]+edge[i].w)
            {
                dis[j]=dis[vertax]+edge[i].w;
                vis0[j]=vertax;
                heap.push({dis[j],j});
            }
        }
        
    }
}
//deque<int> stars;
//void print_stars()
//{
//
//    
//    stars.push_front(n);
//    k=n;
//    while(vis0[k]!=s)
//    {
//        k=vis0[k]; 
//        stars.push_front(k);
//    }
//    stars.push_front(s);
//}
void printf_path(int vertax)
{
    if(vis0[vertax] != -1 ) printf_path(vis0[vertax]);
    cout<<vertax<<'\n';
}
int main()
{
    int a,b,c;
    memset(head,-1,sizeof head);
    memset(vis0,-1,sizeof vis0);
    cin>>m>>n;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            c=1;
            add(a,b,c);
//            add(b,a,c);    
        }
    if(n==1)
    {
        cout<<"1"<<'\n'<<"1"<<'\n';
    }
    else{
    
    
        dijkstra();
        if(dis[n]==0x3f3f3f3f)
        {
            cout<<"-1";
        }
        else{
            cout<<dis[n]+1<<'\n';
            printf_path(n);
//            while(stars.size())
//            {
//                cout<<stars.front()<<'\n';
//                stars.pop_front();
//            }
        }
    }
    return 0;
}

Answer 1

我试着照着你的deque输出的代码写了一个测试，可以正常输出，所以问题应该不在这里