1 #include <iostream>  2 #include <sstream>  3 #include <cstdio>  4 #include <cstring>  5 #include <cmath>  6 #include <string>  7 #include <vector>  8 #include <set>  9 #include <cctype> 10 #include <algorithm> 11 #include <cmath> 12 #include <deque> 13 #include <queue> 14 #include <map> 15 #include <stack> 16 #include <list> 17 #include <iomanip> 18 using namespace std; 19  20 #define INF 0x7fffffff 21 #define maxn 100000+10 22  23 int n, m; 24 vector<int> g[maxn];//用以存放互相连通的房间 25 vector<int> col[maxn];//用以存放走廊颜色 26 int step[maxn];//存放由n到i的最短步数 27 int ans[maxn*2]; 28 int vis[maxn]; 29 void init() 30 { 31     for(int i = 0; i < maxn; i++) 32     { 33         g[i].clear(); 34         col[i].clear(); 35     } 36     memset(step, -1, sizeof(step)); 37     memset(ans, 0, sizeof(ans)); 38     memset(vis, 0, sizeof(vis)); 39 } 40 //==============获得到n的最少步数(逆向由n到1)=========== 41 void bfs1() 42 { 43     queue<int> q; 44     q.push(n); 45     step[n] = 0;//初始，由n到n的最短步数为0 46     while(!q.empty()) 47     { 48         int u = q.front(); q.pop(); 49         int sz = g[u].size(); 50         for(int i = 0; i < sz; i++) 51         { 52             int v = g[u][i]; 53  54             if(v == 1) 55             { 56                 step[v] = step[u]+1; 57                 return ; 58             } 59  60             if(step[v] == -1) 61             { 62                 step[v] = step[u]+1; 63                 q.push(v); 64             } 65         } 66     } 67     return ; 68 } 69  70 //==========获得最少步数时的最小走廊颜色=========== 71 void bfs2() 72 { 73     queue<int> q; 74     q.push(1); 75     while(!q.empty()) 76     { 77         int u = q.front(); q.pop(); 78         /// 79         if(!step[u])    return ;//到达n 80         /// 81         int mmin = INF; 82         int sz = g[u].size(); 83         for(int i = 0; i < sz; i++) 84         { 85             int v = g[u][i]; 86             if(step[v] == step[u]-1) 87             { 88                 mmin = min(mmin, col[u][i]);//注意理解c[u][i]与g[u][i]间的联系--c[u][i]是u连接g[u][i]的走廊颜色 89             } 90         } 91         //==========以上获得了从1出发最短路中每步的最小色 92  93         int tmp_step = step[1] - step[u];//从1到u的步数，即出发第tmp_step步 94         //ans[tmp_step] = (ans[tmp_step] == 0 ? mmin : min(mmin, ans[tmp_step])); 95         if(ans[tmp_step] == 0)  ans[tmp_step] = mmin; 96         else ans[tmp_step] = min(ans[tmp_step], mmin); 97  98         for(int i = 0; i < sz; i++) 99         {100             int v = g[u][i];101             ///该处判断条件很重要,把走过的路做标记102             if(!vis[v] && step[v] == step[u]-1 && mmin == col[u][i])103             {104                 vis[v] = 1;105                 q.push(v);106             }107         }108     }109     return ;110 }111 int main()112 {113     //===================input=====================114     while(~scanf("%d%d", &n, &m))115     {116         init();117         while(m--)118         {119             int a, b, c;120             scanf("%d%d%d", &a, &b, &c);121             if(a == b) continue;122             g[a].push_back(b);123             g[b].push_back(a);124             col[a].push_back(c);125             col[b].push_back(c);126         }127         //===============逆向bfs===============128         //============获得最短步数=============129         bfs1();130         //===============正向bfs===============131         //==========获得每步的走廊颜色=========132         bfs2();133 134         printf("%d\n", step[1]);135         for(int i = 0; i < step[1]; i++)136         {137             if(i) printf(" ");138             printf("%d", ans[i]);139         }140         printf("\n");141     }142     return 0;143 }