Hướng giải của Hành trình có điều kiện

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

Quy hoạch động kết hợp tìm đường đi ngắn nhất. Ta định nghĩa trạng thái \(dist[u][c]\) là chi phí nhỏ nhất để di chuyển từ \(S\) tới đỉnh \(u\) sử dụng đúng \(c\) lối đi hiểm trở. Do đồ thị có thể có cạnh âm, ta chạy thuật toán Bellman-Ford để cập nhật các trạng thái. Vì số lượng trạng thái tối đa là \(N imes (C + 1)\), ta lặp cập nhật tối đa \(N imes (C + 1)\) lần để tìm kết quả tối ưu.

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;
    int h;
};

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

    int n, m, max_c, s, t;
    if (!(cin >> n >> m >> max_c >> 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 >> edges[i].h;
    }

    vector<vector<long long>> dist(n + 1, vector<long long>(max_c + 1, INF));
    dist[s][0] = 0;

    int limit_iters = n * (max_c + 1);
    for (int iter = 1; iter <= limit_iters; iter++) {
        bool updated = false;
        for (const auto& e : edges) {
            for (int c = 0; c <= max_c; c++) {
                if (dist[e.u][c] == INF) continue;
                int next_c = c + e.h;
                if (next_c <= max_c) {
                    if (dist[e.u][c] + e.w < dist[e.v][next_c]) {
                        dist[e.v][next_c] = dist[e.u][c] + e.w;
                        updated = true;
                    }
                }
            }
        }
        if (!updated) break;
    }

    long long ans = INF;
    for (int c = 0; c <= max_c; c++) {
        ans = min(ans, dist[t][c]);
    }

    if (ans == INF) cout << "impossible\n";
    else cout << ans << "\n";

    return 0;
}

Nhận xét

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