Lời giải: Đường đi có chi phí nhỏ nhất

Tư duy

Hệ thống tuyến giao hàng không tạo vòng khép kín, đồng thời mọi chi phí đều dương, nên ta hoàn toàn có thể áp dụng quy hoạch động theo thứ tự đảm bảo để tìm đường đi rẻ nhất.

Phương pháp

1. Bước 1: Sắp xếp các kho theo thứ tự đảm bảo (topo sort Kahn) trong \(O(N + M)\). Vì không có vòng khép kín, thứ tự này luôn tồn tại và duy nhất khi cố định cách chọn đỉnh khi nhiều đỉnh cùng bán bậc vào bằng \(0\).
2. Bước 2: Gọi dp[v] là chi phí nhỏ nhất để đến được kho \(v\) từ kho \(1\). Khởi tạo dp[1] = 0, các dp[v] còn lại là \(+\infty\) (chưa tới được).
3. Bước 3: Duyệt các kho theo thứ tự đảm bảo. Với mỗi kho \(u\), với mỗi tuyến \(u \to v\) có chi phí \(w\), cập nhật: \[dp[v] = \min\!\left(\,dp[v],\ dp[u] + w\,\right)\]
4. Kết quả: dp[N] là chi phí nhỏ nhất cần tìm.

Tại sao thuật toán đúng?

• Thứ tự đảm bảo đảm bảo khi xét \(u\) thì tất cả các kho có tuyến đi vào \(u\) đều đã được xử lý xong.
• Như vậy, khi cập nhật dp[v], giá trị dp[u] đã được tính đúng là chi phí nhỏ nhất để tới \(u\).
• Vì đồ thị không có vòng khép kín, mỗi đường đi từ \(1\) đến \(N\) chỉ đi qua mỗi kho tối đa một lần → không có vấn đề "duyệt lặp".

Đánh giá độ phức tạp

• Sắp xếp: \(O(N + M)\).
• Quy hoạch động: \(O(N + M)\).
• Tổng: \(O(N + M)\) thời gian, \(O(N + M)\) bộ nhớ.

Mã nguồn tham khảo (C++)

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

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

    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, long long>>> adj(N + 1);
    vector<int> indeg(N + 1, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (indeg[i] == 0) q.push(i);
    }

    const long long INF = 4e18;
    vector<long long> dp(N + 1, INF);
    dp[1] = 0;

    vector<int> order;
    order.reserve(N);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (auto& [v, w] : adj[u]) {
            if (dp[u] + w < dp[v]) {
                dp[v] = dp[u] + w;
            }
            if (--indeg[v] == 0) q.push(v);
        }
    }

    cout << dp[N] << "\n";
    return 0;
}