本题昨晚和一个大佬讨论了一下，有了一个初步的解决方案，但是今天下午实现的时候发现仍有bug。

完整的思路为：

1. d数组为反向dfs获得的新图的结构。即在新图中，u的下一个结点为v需满足，d[v] == d[u] - 1。

2. 新图为有向无环图。

3. 问题转化为：有一个DAG，边有权，给定起点s，终点t，（此时有个特殊的性质——从s到t的所有路径长度相同）找一条从s到t的路径，使得一路的权值序列的字典序最小。

4. 每对队列中的一个新弹出的结点进行扩展时，找到其权值最小的那个条边，此时假设该边为 u - v，接下来在根据此边color值是否小于V的当前颜色值color[v]来决定是否进队列，同时更新farther[v]。（记录farther[u]或者farther[v]都行）。这样其实有个bug，此时仅仅是s到v的路径满足了题意中的字典序最小的要求，但是考虑到一种特殊情况，与u并列的u'的下一条边为u' - v'，如果其颜色值小于color[v]，并且从v引出的路率先到达终点t，那么结果并非字典序最小。 

eg:

从1到58

1 10 1

1 46 1

10 22 1

46 22 1

10 50 0

50 58 1

22 58 1

void bfs2(){    for(int i = 1; i <= n; i++){        colors[i] = INT_MAX;    }    queue
      
       q;    q.push(1);    //int cur_layer_min = INT_MAX;    while(!q.empty()){        int u = q.front(); q.pop();        if(u == n){            break;        }        int min_color = INT_MAX;        for(int i = 0; i < G[u].size(); i++){            int v = G[u][i].first;            if(d[v] == d[u] - 1)                min_color = min(min_color, G[u][i].second);        }        for(int i = 0; i < G[u].size(); i++){            int v = G[u][i].first;            if(d[v] == d[u] - 1 && G[u][i].second == min_color){                if(min_color < colors[v]){                    //cur_layer_min = min_color;                    fa[v] = u;                    q.push(v);                    colors[v] = min_color;                }            }        }    }    vector
       
        vec;    for(int i = n; i != 1; i = fa[i]){        cout << i << endl;        vec.push_back(colors[i]);    }    cout << d[1] << endl;    for(int i = vec.size() - 1; i >= 0; i--){        cout << vec[i];        if(i) cout << " ";    }    cout << endl;}
       
      

 

重新审视此问题，其实就是一颗层次树，找每个层的最小值，从这些结点继续扩展下去。

AC代码

#include
      
       using namespace std;typedef pair
       
        Pair;const int maxn = 100000 + 3;int n, m;vector
        
         G[maxn];int d[maxn];bool vis[maxn];void  bfs1(){    memset(vis, 0, sizeof(vis));    queue
         
          q;    q.push(n);    vis[n] = true;    d[n] = 0;    while(!q.empty()){        int u = q.front(); q.pop();        if(u == 1){            break;        }        for(int i = 0; i < G[u].size(); i++){            int v = G[u][i].first;            if(!vis[v]){                q.push(v);                vis[v] = true;                d[v] = d[u] + 1;            }        }    }}int q[maxn];void bfs3(){    int head = 0, tail = 0;    q[tail++] = 1;    vector
          
           ans;    while(head !=  tail){        if(q[head] == n){            break;        }        int min_color = INT_MAX;        int head_copy = head;        while(head != tail){            int u = q[head++];            for(int i = 0; i < G[u].size(); i++){                int v = G[u][i].first;                if(d[v] == d[u] - 1){                    min_color = min(min_color, G[u][i].second);                }            }        }        ans.push_back(min_color);        int head = head_copy;        set
           
            s; while(head != tail){ int u = q[head++]; for(int i = 0; i < G[u].size(); i++){ int v = G[u][i].first; if(d[v] == d[u] - 1 && min_color == G[u][i].second){ s.insert(v); } } } for(auto item : s){ q[tail++] = item; } } cout << ans.size() << endl; cout << ans[0]; for(int i = 1; i < ans.size(); i++){ cout << ' ' << ans[i]; } cout << endl;}void solve(){ memset(d, -1, sizeof(d)); bfs1(); bfs3();}int main(){ freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); while(cin >> n >> m && n){ for(int i = 1; i <= n; i++){ G[i].clear(); } for(int i = 0; i < m; i++){ int u, v, color; cin >> u >> v >> color; G[u].push_back(make_pair(v, color)); G[v].push_back(make_pair(u, color)); } solve(); } return 0;}
           
          
         
        
       
      

 

收获：

1. 理清题意，划定算法类别，并且研究此问题和典型、常规的题目的区别在哪里，需要在哪里做何种变化？

2. 犯了memset(a, INT_MAX, sizeof(a))的错误。