//基于邻接矩阵的Dijstra算法-输出路径  1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6  7 int n,m; 8 int map[1009][1009]; 9 int path[1009];10 int dis[1009];11 bool used[1009];12 const int maxint=999999999;13 14 void dijk()15 {16     memset(path,-1,sizeof(path));17     memset(used,0,sizeof(used));18     int i,j,k;19     used[1]=1;20 21     for(i=1;i<=n;i++)22         dis[i]=map[1][i];23 24     for(i=1;i
         
          dis[j])30             {31                 tmin=dis[j];k=j;32             }33         }34 35         used[k]=1;36         for(j=1;j<=n;j++)37         {38             if(used[j]==0)39             {40                 if(dis[k]+map[k][j]
          

ss;50 ss.push(n);51 i=n;52 while(path[i]!=-1)53 {54 i=path[i];55 ss.push(i);56 }57 if(dis[n]==maxint)58 {59 printf("-1\n");60 return ;61 }62 ss.push(1);63 printf("%d\n",dis[n]+1);64 65 while(!ss.empty())66 {67 printf("%d\n",ss.top());68 ss.pop();69 }70 }71 72 int main()73 {74 while(scanf("%d%d",&m,&n)!=EOF)75 {76 int i,j;77 for(i=1;i<=n;i++)78 {79 for(j=1;j<=n;j++)80 map[i][j]=maxint;81 }82 83 int a,b;84 for(i=1;i<=m;i++)85 {86 scanf("%d%d",&a,&b);87 map[a][b]=1;88 }89 90 dijk();91 }92 }