bfs

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

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
const int maxn = 100005;
const int INF = 1 << 30;

bool vis[maxn];
int d[maxn];
int ans[maxn];
vector<int> G[maxn];
vector<int> E[maxn];

void bfs_01(int n);
void bfs_02();

int main()
{
    // freopen("in.txt", "r", stdin);
    // clock_t start, end;
    // start = clock();

    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(vis, false, sizeof(vis));
        memset(d, 0, sizeof(d));
        memset(ans, 0, sizeof(ans));
        for(int i = 0; i < maxn; ++i) G[i].clear();
        for(int i = 0; i < maxn; ++i) E[i].clear();

        for(int i = 0; i < m; ++i)
        {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            if(u == v) continue;
            G[u].push_back(v);
            G[v].push_back(u);
            E[u].push_back(c);
            E[v].push_back(c);
        }
        bfs_01(n);
        memset(vis, false, sizeof(vis));
        bfs_02();

        printf("%d\n", d[1]);
        printf("%d", ans[1]);
        for(int i = 2; i <= d[1]; ++i)
            printf(" %d", ans[i]);
        printf("\n");
    }
    // end = clock();
    // printf("Run time: %fS\n",(double)(end - start) / CLOCKS_PER_SEC);
    return 0;
}

// 反向遍历一次
void bfs_01(int n)
{
    queue<int> Q;
    Q.push(n); vis[n] = true;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();

        int size = G[u].size();
        for(int i = 0; i < size; ++i)
        {
            int v = G[u][i];
            if(vis[v]) continue;
            Q.push(v);
            vis[v] = true;
            d[v] = d[u] + 1;
        }
    }
}

void bfs_02()
{
    vector<int> next;
    next.push_back(1);

    for (int i = 1; i <= d[1]; ++i) 
    {
        // 第i层，遍历next节点，找到下一层中最小颜色
        int min_c = INF;
        for (int j = 0; j < next.size(); ++j) 
        {
            // 对于每个节点，找到下一层中最小颜色
            int u = next[j];
            for (int p = 0; p < G[u].size(); ++p) 
            {
                int v = G[u][p];
                if (d[v] == d[u] - 1 && min_c > E[u][p]) min_c = E[u][p];
            }
        }
        ans[i] = min_c;
        vector<int> newnext;

        for (int j = 0; j < next.size(); ++j) 
        {
            int u = next[j];
            for (int p = 0; p < G[u].size(); ++p) 
            {
                int v = G[u][p];
                if (d[v] == d[u] - 1 && min_c == E[u][p] && !vis[v]) 
                {
                    newnext.push_back(v);
                    vis[v] = true;
                }
            }
        }
        next = newnext;
    } 
}