Hiểu bài toán

Bài toán yêu cầu tìm đường đi ngắn nhất từ máy 1 đến máy N trong đồ thị có hướng (vô hướng nhưng coi như 2 cạnh có hướng) có cạnh trọng số nguyên. Chúng ta có K thiết bị tăng tốc, mỗi thiết bị có thể giảm một nửa trọng số của một cạnh. Các thiết bị có thể được đặt trên cùng một cạnh nhiều lần (ví dụ K=2 đặt 2 lần lên cùng cạnh thì trọng số chia 4). Cần tìm tổng thời gian nhỏ nhất có thể sau khi phân bổ tối đa K thiết bị.

Dạng bài này là bài toán tìm đường đi ngắn nhất có giới hạn số lần sử dụng 'kỹ năng' (giảm chi phí cạnh). Kỹ năng chỉ có thể dùng trên các cạnh cụ thể.

Các cách tiếp cận

Cách Dijkstra với state (Optimized)

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

const int MAXN = 1005;
const int MAXK = 12;
const double INF = 1e18;

int n, m, k;
struct Edge {
    int to;
    int cost;
};
vector<Edge> adj[MAXN];

double dist[MAXN][MAXK]; // dist[u][j]: chi phí đến u dùng j thiết bị

struct State {
    double d;
    int u;
    int k;
    bool operator>(const State& other) const {
        return d > other.d;
    }
};

void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dist[i][j] = INF;
        }
    }
    dist[1][0] = 0;

    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        State top = pq.top();
        pq.pop();
        double d = top.d;
        int u = top.u;
        int k_used = top.k;

        if (d > dist[u][k_used]) continue;

        for (auto& e : adj[u]) {
            // Truong hop khong su dung thiet bi
            if (dist[e.to][k_used] > d + e.cost) {
                dist[e.to][k_used] = d + e.cost;
                pq.push({dist[e.to][k_used], e.to, k_used});
            }
            // Truong hop su dung thiet bi (neu du so luong)
            if (k_used < k) {
                double new_cost = d + (double)e.cost / 2.0;
                if (dist[e.to][k_used + 1] > new_cost) {
                    dist[e.to][k_used + 1] = new_cost;
                    pq.push({new_cost, e.to, k_used + 1});
                }
            }
        }
    }

    double ans = INF;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dist[n][i]);
    }
    cout << fixed << setprecision(2) << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

• Time Complexity: O(M * K * log(N * K))
• Space Complexity: O(N * K)

Đây là cách tiếp cận trực tiếp và tối ưu nhất cho ràng buộc K ≤ 10. Ta coi trạng thái là (đỉnh, số thiết bị đã dùng). Dijkstra được sửa đổi để xử lý các cạnh:

1. Chuyển tiếp không dùng thiết bị: Chi phí + C.
2. Chuyển tiếp có dùng thiết bị (nếu k_used < K): Chi phí + C/2. .Hàng đợi Ưu tiên (Min-Heap) chọn ra node có tổng thời gian nhỏ nhất để mở rộng. Kích thước trạng thái là N * (K+1). Độ phức tạp là O(log(NK) * (M(K+1))) nhưng thực tế chỉ duyệt qua các cạnh của node đang xét, nhân với hệ số K. Với N=1000, M=10^5, K=10, tổng số trạng thái ~10^4, số cạnh ~2*10^6, hoàn toàn chạy được.

Cách Chia Dãy (Segmentation) - Phân tích thô

// Pseudocode logic do code tham lam chua hoan chinh
// 1. Tim duong di ngan nhat khong su dung thiet bi (Dijkstra binh thuong)
// 2. Danh dau cac canh thuoc duong di do
// 3. Tinh toan loi ich cua viec dat thiet bi tren tung canh trong duong di
// 4. Sap xep loi ich giam dan, chon K canh loi ich nhat

void solve_greedy_segment() {
    // ... (Code Dijkstra lay duong di) ...
    // ... (Code loc cac canh thuoc duong di) ...
    // ... (Code tinh tong thoi gian moi khi chon them 1 thiet bi) ...
}

• Time Complexity: O(K * (M log N))
• Space Complexity: O(N + M)

Phương pháp này dựa trên giả định 'tham lam': ta sẽ chỉ đặt thiết bị trên các cạnh thuộc đường đi ngắn nhất ban đầu. Tuy nhiên, điều này KHÔNG LUÔN ĐÚNG. Việc đặt thiết bị có thể làm thay đổi cấu trúc đường đi, dẫn đến một đường đi mới (không phải đường đi ban đầu) trở thành đường đi ngắn nhất. Ví dụ, việc giảm chi phí một cạnh có thể khiến ta rẽ vào nhánh khác rẻ hơn. Do đó, phương pháp này chỉ đúng khi K rất nhỏ và đồ thị đơn giản.

Cách Quy hoạch động trên Dãy con (Dynamic Programming on Shortest Path)

// Pseudocode
// 1. Dijkstra để tính dist[u]: khoảng cách từ 1 -> u
// 2. Dijkstra ngược (từ N) để tính rdist[u]: khoảng cách từ u -> N
// 3. Xét tất cả các cạnh (u, v, c):
//    Khoảng cách đi qua cạnh này là dist[u] + c + rdist[v]
//    Nếu ta đặt t thiết bị lên cạnh này, thời gian là dist[u] + c/(2^t) + rdist[v]
// 4. Quy hoạch động:
//    dp[i][j]: thời gian ngắn nhất đến N khi đã dùng i thiết bị trên đường đi.
//    Hoặc: Cải tiến từ Method 1 (Dijkstra State) là tối ưu nhất.

• Time Complexity: O(M log N + K * M)
• Space Complexity: O(N + M)

Một cách tiếp cận khác (thường bị nhầm là tối ưu) là tính toán trước các khoảng cách từ nguồn và đến đích. Tuy nhiên, việc đặt thiết bị trên một cạnh cụ thể có thể tạo ra một đường đi mới hoàn toàn. Phương pháp 'Quy hoạch động trên dãy con' trong các giải pháp tham khảo thường là biến thể của Dijkstra State hoặc một thuật toán tham lam phức tạp. Phương pháp chuẩn mực và an toàn nhất cho ràng buộc này là Dijkstra State.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể mô hình hóa thành bài toán tìm đường đi ngắn nhất trên đồ thị có trạng thái (State Graph) với kích thước N*(K+1).
• Mỗi cạnh đồ thị ban đầu tương đương với 2 loại cạnh trong đồ thị trạng thái: cạnh thường và cạnh đã được áp dụng thiết bị tăng tốc.

Lỗi thường gặp

• Sử dụng thuật toán tham lam (chọn các cạnh có chi phí giảm nhiều nhất trên đường đi ban đầu) sẽ sai do có thể tạo ra các đường đi mới.
• Quên xử lý trường hợp có nhiều hơn một cạnh giữa hai node (trọng số nhỏ nhất sẽ được chọn tự động trong Dijkstra).