思路与算法

先从终点BFS得到每个点到终点的最少边数。起点作为初始候选集；每层只考虑距离减少1的边，在整个候选集中选最小颜色，再把所有能走这类边的终点作为下一层候选。

正确性说明

距离每步减少1保证最终路径边数最少。对颜色前缀归纳，候选集恰是所有具有当前最优前缀的路径终点；下一位只需在这些点的合法边中取最小色，保留所有并列终点，因而不会丢失未来更优的后缀。

复杂度

BFS、各层扫描及去重累计O(n+m)，包括距离/标记初始化。空间O(n+m)，另输出长度≤n-1。多组按各组规模求和。

易错点

不能只保留一个最小颜色终点。颜色按整数比较。自环不会使距离下降；无路输出-1及空颜色行。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> a(n);
        for (int i = 0, u, v, c; i < m; i++) {
            cin >> u >> v >> c;
            --u;
            --v;
            a[u].push_back({v, c});
            a[v].push_back({u, c});
        }
        vector<int> d(n, -1), q{n - 1};
        d[n - 1] = 0;
        for (size_t i = 0; i < q.size(); i++)
            for (auto e : a[q[i]])
                if (d[e.first] < 0) {
                    d[e.first] = d[q[i]] + 1;
                    q.push_back(e.first);
                }
        cout << d[0] << '\n';
        if (d[0] < 0) {
            cout << '\n';
            continue;
        }
        vector<int> front{0};
        vector<char> seen(n);
        seen[0] = 1;
        for (int step = d[0]; step; step--) {
            int best = INT_MAX;
            for (int u : front)
                for (auto e : a[u])
                    if (d[e.first] == d[u] - 1)
                        best = min(best, e.second);
            vector<int> next;
            for (int u : front)
                for (auto e : a[u])
                    if (d[e.first] == d[u] - 1 && e.second == best && !seen[e.first]) {
                        seen[e.first] = 1;
                        next.push_back(e.first);
                    }
            cout << best << (step == 1 ? '\n' : ' ');
            front.swap(next);
        }
    }
}