题目链接：

思路：题目的意思是求给定的起点到终点的最短路径序列，并且这个序列的字典顺序最小。我们可以先求最短路，然后对那些在最短路上的点进行深度优先搜索。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 10 const int MAXN=55555; 11 const int inf=1<<30; 12 vector
             
              g[MAXN],vet,ans; 13 int n,st,ed; 14 15 int dist[MAXN]; 16 bool mark[MAXN]; 17 18 struct Node{ 19 int v,d; 20 Node(int vv,int dd){ 21 v=vv,d=dd; 22 } 23 bool operator < (const Node &p) const { 24 if(p.d!=d)return p.d
              
               que; 35 que.push(Node(st,0)); 36 dist[st]=0; 37 while(!que.empty()){ 38 Node p=que.top(); 39 que.pop(); 40 if(mark[p.v])continue; 41 mark[p.v]=true; 42 for(int i=0;i<(int)g[p.v].size();i++){ 43 int v=g[p.v][i]; 44 if(mark[v])continue; 45 if(dist[p.v]+1
               

st; 56 if(u==ed)return true; 57 for(int i=0;i

::iterator iter; 62 for(iter=st.begin();iter!=st.end();iter++){ 63 ans.push_back(*iter); 64 if(dfs(*iter))return true; 65 ans.pop_back(); 66 } 67 return false; 68 } 69 70 71 72 int main() 73 { 74 int _case,t=1; 75 scanf("%d",&_case); 76 while(_case--){ 77 scanf("%d",&n); 78 vet.clear(); 79 ans.clear(); 80 for(int i=1;i