correct

原始文件为 cpp 代码，本文是转换后的 Markdown 文件。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#define maxn 100005
#define maxm 200005
#define inf 1<<30
using namespace std;
int n, m;
struct edge {
    int node1, node2, color;
    edge(int n1, int n2, int n3): node1(n1), node2(n2), color(n3) {}
};
bool vis[maxn];
int dis[maxn];
vector<int> graph[maxn], ans; //graph[i][j]=p, 则edges[p].node1==i; //ans记录最短路径颜色 
vector<edge> edges;
void reset() {
    memset(vis, false, sizeof(vis));
    memset(dis, inf, sizeof(dis));
    for (int i=0; i<maxn; ++i) graph[i].clear();
    edges.clear();
    ans.clear();
}
void build (int n1, int n2, int c) {
    edges.push_back(edge(n1,n2,c));
    graph[n1].push_back( (edges.size()-1) );
}
//从终点n开始倒着bfs, 记录每个节点到终点的最短路程dis 
void rev_bfs() {
    vis[n]=true;
    dis[n]=0;
    queue<int> que;
    que.push(n);
    while (!que.empty()) {
        int last=que.front();
        que.pop();
        for (int i=0; i<graph[last].size(); ++i) {
            edge ed = edges[graph[last][i]];
            if (!vis[ed.node2]) {
                vis[ed.node2]=true;
                dis[ed.node2]=dis[last]+1;
                que.push(ed.node2);
            }
        }
    }
    printf("%d\n",dis[1]);
}
// 从起点0开始, 找所有dis下降为1的路径，从中选择颜色编号最小的路径前进
// (多条路径颜色相同时全部要搜索下一层比较)，直到终点n. 
void bfs() {
    vector<int> next;
    next.push_back(1);
    vis[1]=true;
    for (int i=1; i<=dis[1]; ++i) {
        int min_c=inf;
        for (int j=0; j<next.size(); ++j) {
            int k=next[j];
            for (int p=0; p<graph[k].size(); ++p) {
                int tmp=graph[k][p];
                if (!vis[edges[tmp].node2] && dis[edges[tmp].node2]-dis[k]==-1) {
                    min_c= min (min_c, edges[tmp].color);
                }
            }
        }
        ans.push_back(min_c);
        vector<int> newnext;
        for (int j=0; j<next.size(); ++j) {
            int k=next[j];
            for (int p=0; p<graph[k].size(); ++p) {
                int tmp=graph[k][p];
                if (!vis[edges[tmp].node2] && dis[edges[tmp].node2]-dis[k]==-1 && edges[tmp].color==min_c) {
                    newnext.push_back(edges[tmp].node2);
                    vis[edges[tmp].node2]=true;
                }
            }
        }
        next=newnext;
    } 
}
int main () {
    // freopen("in.txt","r",stdin);
    while (scanf ("%d%d",&n,&m)==2) {
        reset();
        for (int i=1; i<=m; ++i) {
            int n1, n2, c;
            scanf("%d%d%d",&n1,&n2,&c);
            build(n1,n2,c);
            build(n2,n1,c);
        }
        rev_bfs();
        memset(vis,false,sizeof(vis));
        bfs();
        for (int i=0; i<ans.size(); ++i) {
            printf("%d",ans[i]);
            if (i<ans.size()-1) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}