J

ImmatureDreamer · 2026-07-19 18:47:37 · 题解

首 A 报道。

注意到边权很小（不超过 8），可按边权升序搜索路径，并维护下一步能到达的点，进行 DFS。这样由于每次都走最小边权，能保证字典序。可以从能到达所有点的虚点 0 开始，最后补上一些 -1。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5 + 5;

int n, m, k;
vector<int> G[N][10];

void dfs(int d, vector<int> now){
    for(int i = 1; i <= 8; ++ i){
        vector<int> nxt;
        for(int u : now)
            for(int v : G[u][i]){
                cout << d + 1 << "\n";
                -- k;
                if(!k) exit(0);
                nxt.push_back(v);
            }
        if(!nxt.empty())
            dfs(d + 1, nxt);
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; ++ i){
        int u, v, w;
        cin >> u >> v >> w;
        G[u][w].push_back(v);
    }
    vector<int> all_points;
    for(int i = 1; i <= n; ++ i)
        all_points.push_back(i);
    dfs(0, all_points);
    while(k --)
        cout << "-1\n";

    return 0;
}