话不多说，直接看题：

首先，这个不是按照字典序的顺序，而是以只要1先做，在满足后让2先做。。。。

就是让数字小的放前面做+拓扑排序。

我们可以先做1，看看它的前驱。

举个例子：

我们肯定要把1放前面做，然后就确定把1的前驱及其相连放前面。

我们再看2，2没有，那就把2的前驱及其相连放1后面。

看3，我们把3，6放最前面，同理，把5，4放在3后面，于是我们可以得到63541.

我们发现这样子实现起来比较困难，这是因为限制关系造成的，我们知道首先要选的肯定在无前驱的点上，但至于要哪个无法根据现在的情况推断，这就造成了实现的复杂性。

于是，我们可以反着看，我们把边反一下，把取第1个的思路换成取倒数第n个，这样子，最后一个肯定在无前驱的点上，而我们只要选其中max的，然后再根据它解锁倒数第2个的可能的点。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int d,n,m,x,y,ans[100010],inc[100010],head[100010],cnt;
struct node{int next,dian;
}edge[100010];
priority_queue<int> q;
void merge(int x,int y){edge[++cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
bool tuopu(){while(!q.empty()) q.pop();for(int i=1;i<=n;i++){if(inc[i]==0){q.push(i);}}int ck=0;while(!q.empty()){int hh=q.top();q.pop();ans[++ck]=hh;for(int i=head[hh];i!=-1;i=edge[i].next){inc[edge[i].dian]--;if(inc[edge[i].dian]==0) q.push(edge[i].dian);}}if(ck<=n-1) return 0;else return 1;
}
int main(){cin>>d;while(d--){scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));memset(inc,0,sizeof(inc));cnt=0;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);merge(y,x);inc[x]++;}if(tuopu()==0) printf("Impossible!\n");else{for(int i=n;i>=1;i--) printf("%d ",ans[i]);cout<<endl;}}
}

让我们再了解一下超级源点的应用吧：

我们再添加一个点使他与k个点的距离为0，因此，问题就转化成了单源点的问题，跑个迪杰斯特拉即可。

接题：

法1.BFS：

我们再记录一下当前走的方向，以转弯次数为顺序，用0/1BFS即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,zx,zy,sx,sy;
char a[105][105],c;
bool vis[105][105];
struct node{int x,y,dir,ci;
}qi;
int di[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
deque<node> q;
int bfs(node qi1){memset(vis,0,sizeof(vis));if(!q.empty()) q.pop_back();q.push_front(qi1);while(!q.empty()){node ck=q.front();vis[ck.x][ck.y]=1;q.pop_front();if(ck.x==zx&&ck.y==zy) {return ck.ci;}for(int i=0;i<4;i++){node hh;hh.x=ck.x+di[i][0];hh.y=ck.y+di[i][1];if(hh.x<=0||hh.y<=0||hh.x>n||hh.y>n) continue;if(a[hh.x][hh.y]=='x') continue;if(vis[hh.x][hh.y]==1) continue;if(ck.dir==abs(di[i][0])){q.push_front({hh.x,hh.y,ck.dir,ck.ci});}else{q.push_back({hh.x,hh.y,1-(ck.dir),ck.ci+1});  }}}return -1;
}
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>c;a[i][j]=c;if(c=='A'){sx=i;sy=j;}if(c=='B'){zx=i;zy=j;}}}int a1=bfs({sx,sy,1,0});int b1=bfs({sx,sy,0,0});if(a1==-1||b1==-1) cout<<max(a1,b1);else cout<<min(a1,b1);
}

法2.建图：

下面为AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,sx,sy,zx,zy;
char a[105][105],c;
int head[100000],cnt;
struct node{int dian,len,next;
}edge[500000];
void merge(int x,int y,int v){edge[++cnt].dian=y;edge[cnt].len=v;edge[cnt].next=head[x];head[x]=cnt;
}
int dis[40000+10];
bool vis[40010];
struct ty{int dian,dis1;bool operator<(const ty &a) const{return dis1>a.dis1;}
};
priority_queue<ty> q;
int dij(int s,int t){q.push({s,0});dis[s]=0;while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.dian]==1) continue;vis[ck.dian]=1;for(int i=head[ck.dian];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(vis[i1]==1) continue;if(dis[i1]>dis[ck.dian]+edge[i].len){dis[i1]=dis[ck.dian]+edge[i].len;q.push({i1,dis[i1]});}}}if(dis[t]>=0x3f) return -1;else return dis[t];}
signed main(){cin>>n;memset(dis,0x3f,sizeof(dis));memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>c;a[i][j]=c;if(c=='A'){sx=i;sy=j;}if(c=='B'){zx=i;zy=j;}}}for(int i=1;i<=n*n;i++){for(int j=1;j<=4;j++){for(int k=1;k<=4;k++){if(k!=j){if((k+j)%2==0)  merge(4*(i-1)+j,4*(i-1)+k,0);else merge(4*(i-1)+j,4*(i-1)+k,1);}}}}for(int i=1;i<=n;i++){for(int j=2;j<=n;j++){if(a[i][j]=='x'||a[i][j-1]=='x'){merge((i-1)*4*n+(j-1)*4+1,(i-1)*4*n+(j-1)*4-1,0x3f);merge((i-1)*4*n+(j-1)*4-1,(i-1)*4*n+(j-1)*4+1,0x3f);}else{merge((i-1)*4*n+(j-1)*4+1,(i-1)*4*n+(j-1)*4-1,0);merge((i-1)*4*n+(j-1)*4-1,(i-1)*4*n+(j-1)*4+1,0);}}}for(int i=1;i<=n;i++){for(int j=2;j<=n;j++){if(a[j][i]=='x'||a[j-1][i]=='x'){merge((j-1)*4*n+(i-1)*4+2,(j-2)*4*n+(i-1)*4+4,0x3f);merge((j-2)*4*n+(i-1)*4+4,(j-1)*4*n+(i-1)*4+2,0x3f);}else{merge((j-1)*4*n+(i-1)*4+2,(j-2)*4*n+(i-1)*4+4,0);merge((j-2)*4*n+(i-1)*4+4,(j-1)*4*n+(i-1)*4+2,0);}}}for(int i=1;i<=4;i++) merge(n*n*4+1,4*(n*sx+sy-n-1)+i,0);for(int i=1;i<=4;i++) merge(4*(n*zx+zy-n-1)+i,n*n*4+2,0);cout<<dij(n*n*4+1,n*n*4+2);
}