题目链接：

 

题意： 保证在最短路的时候，输出字典序最小的路径。

方法：

路径上有了权值，可以利用图论的数据结构来BFS，很方便。

逆序BFS，找到每个点距离终点的最短路长 d[x] ;

然后，从起点，沿着 d[u] = d[v] + 1; 的路径，分层BFS，选字典序最小的。找到那个最小字典序的节点之后，从新建队列。直到找完 d[0];

#include 
      
       using namespace std;const int maxn = 100000 + 5;const int INF = 1000000000;struct Edge{    int u,v,c;    Edge(int u=0,int v = 0,int c = 0) : u(u),v(v),c(c) {}};int n,m;vector
       
         edges;vector
        
          G[maxn];void AddEdge(int from,int to,int c){    edges.push_back(Edge(from,to,c));    int idx = edges.size();    G[from].push_back(idx-1);}int d[maxn];bool vis[maxn];vector
         
           ans;void rev_bfs(){    memset(vis, 0, sizeof(vis));    d[n-1] = 0;    vis[n-1] = true;    queue
          
            q;    q.push(n-1);    while(!q.empty())    {        int u = q.front();        q.pop();        for(int i = 0; i < G[u].size(); i++)        {            Edge _edge = edges[G[u][i]];            int v = _edge.v;            if(!vis[v])            {                vis[v] = true;                d[v] = d[u] + 1;                q.push(v);            }        }    }}void bfs(){    memset(vis,0,sizeof(vis));    vector
           
             next; next.push_back(0); vector
            
              ans; for(int i=0; i
             

next2; for(int j=0; j