Hướng giải của Hành trình tối ưu

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Chúng ta cần tối ưu hóa khoảng cách ngắn nhất có cạnh âm, đồng thời tối thiểu hóa số cạnh đi qua làm tie-break. Mỗi trạng thái tại đỉnh \(u\) được lưu trữ dưới dạng cặp {cost, edge_count}. Khi thư giãn các cạnh bằng Bellman-Ford, ta ưu tiên giá trị có chi phí nhỏ hơn, và nếu chi phí bằng nhau thì ưu tiên số cạnh đi qua ít hơn. Đồng thời lưu trữ mảng parent để truy vết hành trình.

Mã nguồn C++ mẫu

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

const long long INF = 1e18;

struct Edge {
    int u, v;
    long long w;
};

struct State {
    long long cost;
    int edges;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, s, t;
    if (!(cin >> n >> m >> s >> t)) return 0;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    vector<State> dist(n + 1, {INF, 1000000000});
    vector<int> parent(n + 1, -1);
    dist[s] = {0, 0};

    for (int i = 1; i < n; i++) {
        for (const auto& e : edges) {
            if (dist[e.u].cost != INF) {
                long long next_cost = dist[e.u].cost + e.w;
                int next_edges = dist[e.u].edges + 1;
                if (next_cost < dist[e.v].cost) {
                    dist[e.v] = {next_cost, next_edges};
                    parent[e.v] = e.u;
                } else if (next_cost == dist[e.v].cost && next_edges < dist[e.v].edges) {
                    dist[e.v].edges = next_edges;
                    parent[e.v] = e.u;
                }
            }
        }
    }

    if (dist[t].cost == INF) {
        cout << "unreachable\n";
    } else {
        cout << dist[t].cost << "\n";
        vector<int> path;
        int curr = t;
        while (curr != -1) {
            path.push_back(curr);
            curr = parent[curr];
        }
        reverse(path.begin(), path.end());
        cout << path.size() << "\n";
        for (int i = 0; i < (int)path.size(); i++) {
            cout << path[i] << (i == (int)path.size() - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.