编辑代码

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>

using namespace std;

struct Order {
    int src;
    int dst;
    int profit;
};

pair<int, vector<int>> calculateMaxProfit(int start, int time, vector<Order>& orders) {
    // 合并相同路线的订单
    map<pair<int, int>, int> merged;
    for (auto& o : orders) {
        merged[{o.src, o.dst}] += o.profit;
    }

    // 构建邻接表
    map<int, vector<pair<int, int>>> adj;
    for (auto& [route, profit] : merged) {
        adj[route.first].emplace_back(route.second, profit);
    }

    // 确定最大位置编号
    int max_loc = start;
    for (auto& [u, neighbors] : adj) {
        max_loc = max(max_loc, u);
        for (auto& [v, _] : neighbors) {
            max_loc = max(max_loc, v);
        }
    }

    // DP表：dp[u][t] = 最大收益
    vector<vector<int>> dp(max_loc + 1, vector<int>(time + 1, -1));
    // 路径记录表
    vector<vector<vector<int>>> path(max_loc + 1, vector<vector<int>>(time + 1));

    // 初始化
    dp[start][0] = 0;
    path[start][0] = {start};

    for (int t = 0; t < time; ++t) {
        for (int u = 1; u <= max_loc; ++u) {
            if (dp[u][t] == -1) continue;

            // 选择停留
            if (dp[u][t + 1] < dp[u][t]) {
                dp[u][t + 1] = dp[u][t];
                path[u][t + 1] = path[u][t];
            } else if (dp[u][t + 1] == dp[u][t]) {
                if (path[u][t] < path[u][t + 1]) {
                    path[u][t + 1] = path[u][t];
                }
            }

            // 选择接单
            for (auto& [v, profit] : adj[u]) {
                if (t + 1 > time) continue;
                
                int new_profit = dp[u][t] + profit;
                if (dp[v][t + 1] < new_profit) {
                    dp[v][t + 1] = new_profit;
                    path[v][t + 1] = path[u][t];
                    path[v][t + 1].push_back(v);
                } else if (dp[v][t + 1] == new_profit) {
                    vector<int> new_path = path[u][t];
                    new_path.push_back(v);
                    if (new_path < path[v][t + 1]) {
                        path[v][t + 1] = new_path;
                    }
                }
            }
        }
    }

    // 找出最大收益
    int max_profit = 0;
    int best_t = 0;
    for (int t = 0; t <= time; ++t) {
        for (int u = 1; u <= max_loc; ++u) {
            if (dp[u][t] > max_profit) {
                max_profit = dp[u][t];
                best_t = t;
            }
        }
    }

    // 收集所有可能的最佳路径
    vector<vector<int>> candidates;
    for (int u = 1; u <= max_loc; ++u) {
        if (dp[u][best_t] == max_profit && !path[u][best_t].empty()) {
            candidates.push_back(path[u][best_t]);
        }
    }

    // 选择字典序最小的路径
    vector<int> best_path = *min_element(candidates.begin(), candidates.end());

    return {max_profit, best_path};
}

int main() {
    int start, time, m;
    cin >> start >> time >> m;

    vector<Order> orders(m);
    for (int i = 0; i < m; ++i) {
        cin >> orders[i].src >> orders[i].dst >> orders[i].profit;
    }

    auto [profit, path] = calculateMaxProfit(start, time, orders);

    cout << profit << endl;
    for (size_t i = 0; i < path.size(); ++i) {
        if (i != 0) cout << " ";
        cout << path[i];
    }
    cout << endl;

    return 0;
}