#include <stdio.h>
  #include <stdlib.h>
  #include <ctype.h>
  #include <conio.h>
 #include <iomanip.h>
 #include <string>
 #include <iostream.h>
 /*#include <realloc.h>*/
 #define ST  110;     //站的順序儲存表示
 #define  STACKINCREMENT 10;

struct Arcnode{
int adj;
int  a;/*luxian  */
struct Arcnode *next;
}Arcnode,*b;

struct VNode
{
int ad;
struct Arcnode *first;
}a[4000];

 struct GC
{int linecharge;
int prevstop;}d[4000];

struct QNode
{ int data;
  struct QNode *next;
  }QNode,*QueuePtr;

struct LinkQueue
{ struct QNode *front,   *rear;
}LinkQueue,S2;

struct SqStack
{int *base;
int *top;
int  stacksize;
}SqStack;

  int EnQueue(struct LinkQueue Q,int e)
{ struct QNode *p;
    p=(struct QNode*)malloc(sizeof(QNode));
     p->data=e;
 /* p->next=NULL; */
   Q.rear->next=p;
  Q.rear=p;
 return e;
}


void InitQueue(struct LinkQueue Q)
{Q.front=(struct QNode*)malloc(sizeof(QNode));
Q.rear= Q.front;
Q.front->next=NULL;


}
 





DeQueue(struct LinkQueue Q)
{  struct QNode *p ;int e;
  p=(struct QNode*)malloc(sizeof(QNode));
if(Q.front==Q.rear) return 0;
else
{p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return e;}
}

int Gethard(struct LinkQueue Q )
{ int e;
	e=Q.rear->data;
return e;}

QueueEmpty(struct LinkQueue Q)
 {if(Q.rear==Q.front) return 0;
   else return 1;}


 void InitStack(struct SqStack S)    /*構造一個空站S*/
{S.base=(int*) malloc(100 * sizeof (int));
S.top=S.base;
S.stacksize=ST;
}


 void Push(struct SqStack S,int e)  /*插入元素e為新的站頂元素*/
{
if(S.top-S.base>=S.stacksize)
{/*S.base=(int*) realloc (S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));*/
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;

}






 pop(struct SqStack S)  /*若站不空，則刪除S的站頂元素，用e返回其值，并返回OK；否則返回ERROR*/
{int e;
if(S.top==S.base)
return 0;
e=*--S.top;
return e;
}

emptystack(struct SqStack S)
{if(S.top==S.base)return 0;
else return 1;}


void main()

{ int p;int s,s1;int i;int Q,j,k,E;
   for(i=1;i<=4000;i++)
    {a[i].ad=i;
   a[i].first=NULL;}

for(i=1;i<=2;i++)
  {cout<<"shuru luxian"<<endl;
   cin>>p;
   cin>>s;cout<<s;
    while(s!=0)
   {cin>>s1;
     b=(struct Arcnode*)malloc(sizeof(Arcnode));
     b->adj=s1;
     b->a=p;cout<<b->a;
     b->next=a[s].first;
     a[s].first=b;
      s=s1;}
   }            /*    輸入鄰接表*/

  cout<<"inpuit  a pos"<<endl ;
   cin>>j;
    b=a[j].first;
    while(b)
    {cout<<b->adj;cout<<b->a;
    b=b->next;}

 cout<<"/n";
  for(i=1;i<=4000;i++)
{d[i].linecharge=0;
d[i].prevstop=0;
  }

cout<<"輸入起點-終點（4位數)";/*Q為起點E為終點*/
 cin>>Q;cout<<Q;cout<<E;
    k=0;cout<<k;
  
 cin>>E;cout<<"輸入起點-終點（2位數)";
 
InitQueue(S2);
 EnQueue(S2,Q);
 EnQueue(S2,0);

while(QueueEmpty(S2)&&Gethard(S2)!=E)
{s=DeQueue(S2);
 if(s!=0)
 {b=a[s].first;
  while(b)
  {j=b->adj;
  if(d[j].linecharge==0)
  {EnQueue(S2,j);
    d[j].linecharge=k;
	d[j].prevstop=s;}
  }
 }
 else if(QueueEmpty(S2))
{k++; EnQueue(S2,0);}
b=b->next;
  }

   


struct SqStack ZH;
k=E;
InitStack(ZH) ;
while(d[k].prevstop!=Q)
{Push(ZH ,d[k].prevstop);
k=d[k].prevstop; }


while(emptystack(ZH))
{k=pop(ZH);
cout<<setw(5)<<k;
}
}