Hướng dẫn giải của Mạng giao thông

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, td_mduong209, nhathvhq123, trungnghia032024

Hiểu bài toán

Bài toán yêu cầu tìm đường đi ngắn nhất (shortest path) từ nút nguồn s đến nút đích t trong một đồ thị có hướng có thể có trọng số dương. Điểm đặc biệt là có một danh sách k đường đi hai chiều được đề xuất xây dựng. Nhiệm vụ là chọn chính xác một đường trong danh sách này để thêm vào đồ thị sao cho khoảng cách ngắn nhất từ s đến t là nhỏ nhất có thể. Nếu không có đường đi, in ra -1.

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

Cách Dijkstra 3 lần (Đếm đường đi qua cạnh đề xuất)
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
const long long INF = 1e18;

struct Edge {
    int v, w;
};

int n, m, k, s, t;
vector<Edge> adj[N], rev[N]; // rev là đồ thị ngược
long long dist_s[N], dist_t[N], dist_inv[N];
int X[N], Y[N], Q[N];

void dijkstra(int start, long long dist[], const vector<Edge> graph[]) {
    for (int i = 1; i <= n; ++i) dist[i] = INF;
    dist[start] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d != dist[u]) continue;
        for (auto& e : graph[u]) {
            if (dist[e.v] > dist[u] + e.w) {
                dist[e.v] = dist[u] + e.w;
                pq.push({dist[e.v], e.v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k >> s >> t;
    for (int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        rev[v].push_back({u, c}); // thêm cạnh ngược
    }
    for (int i = 0; i < k; ++i) {
        cin >> X[i] >> Y[i] >> Q[i];
    }

    // 1. Khoảng cách từ s đến mọi đỉnh
    dijkstra(s, dist_s, adj);

    // 2. Khoảng cách từ mọi đỉnh đến t (dùng đồ thị ngược, từ t chạy về)
    dijkstra(t, dist_t, rev);

    // 3. Khoảng cách giữa các đỉnh trong đồ thị ban đầu (không dùng cạnh đề xuất)
    // Mục đích: đảm bảo khi dùng cạnh (x, y), ta chỉ xét đường đi x -> y trực tiếp
    // hoặc qua các đỉnh trung gian không chứa cạnh đề xuất.
    // Đơn giản nhất là dùng dist_s cho việc này, nhưng cần phân biệt.
    // Thực tế: ta chỉ cần dùng lại dist_s cho đoạn x -> ...
    // Để tránh lặp lại cạnh đề xuất, ta cần tính dist từ x đến t mà không dùng cạnh đề xuất.
    // Tuy nhiên, cách làm chuẩn và dễ hiểu nhất là:
    // Tính dist[x][t] (từ x đến t) trên đồ thị ban đầu.
    // Gọi là dist_inv (từ t về x trên đồ thị ngược) -> chính là dist_t[x] khi chạy Dijkstra từ t trên đồ thị ngược.
    // Wait, dist_t đã là từ t đến mọi đỉnh trên đồ thị ngược, tức là từ mọi đỉnh đến t trên đồ thị gốc.
    // Ta cần thêm 1 lần Dijkstra nữa: từ t chạy trên đồ thị gốc để lấy dist từ t đến mọi đỉnh? Không.
    // Ta cần: dist từ các đỉnh đến t (đã có là dist_t nếu chạy từ t trên đồ thị ngược).
    // Ta cần: dist từ s đến các đỉnh (dist_s).
    // Ta cần: dist từ x đến t (không dùng cạnh đề xuất).
    // Ta cần: dist từ s đến y (không dùng cạnh đề xuất).
    // Để an toàn, ta chỉ cần dùng dist_s[y] và dist_t[x] (tức là khoảng cách từ x đến t).
    // Sai: dist_t[x] là khoảng cách từ x đến t.
    // Vậy bài toán quy về: min(dist_s[x] + Q[i] + dist_t[y], dist_s[y] + Q[i] + dist_t[x])
    // Lưu ý: dist_s và dist_t được tính trên đồ thị ban đầu (không có cạnh đề xuất).
    // Điều này đảm bảo ta không dùng một cạnh đề xuất để đi vào cạnh đề xuất khác.

    long long ans = dist_s[t];
    if (ans == INF) ans = -1;

    // Tính dist từ t đến mọi đỉnh (trên đồ thị gốc) để xử lý trường hợp đi ngược
    // Gọi là dist_s_inv
    long long dist_s_inv[N];
    dijkstra(t, dist_s_inv, adj); // từ t đi đến mọi nơi trên đồ thị gốc

    for (int i = 0; i < k; ++i) {
        int u = X[i], v = Y[i];
        long long w = Q[i];

        // Case 1: s -> u -> v -> t
        if (dist_s[u] != INF && dist_s_inv[v] != INF) {
            long long val = dist_s[u] + w + dist_s_inv[v];
            if (ans == -1 || val < ans) ans = val;
        }

        // Case 2: s -> v -> u -> t
        if (dist_s[v] != INF && dist_s_inv[u] != INF) {
            long long val = dist_s[v] + w + dist_s_inv[u];
            if (ans == -1 || val < ans) ans = val;
        }
    }

    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(K + (M + K) log N)
  • Space Complexity: O(M + N)

Cách tiếp cận này dựa trên quan sát rằng sau khi chọn một cạnh hai chiều (x, y) với trọng số q, đường đi ngắn nhất sẽ có dạng: s -> ... -> x -> y -> ... -> t hoặc s -> ... -> y -> x -> ... -> t.

Ta thực hiện 3 lần Dijkstra:

  1. Chạy Dijkstra từ s để tính khoảng cách từ s đến mọi đỉnh (dist_s).
  2. Chạy Dijkstra từ t trên đồ thị ngược (vì ta cần khoảng cách từ mọi đỉnh đến t, tức là từ t đến mọi đỉnh trên đồ thị ngược) để tính dist_t (lưu ý: dist_t[u] là khoảng cách từ u đến t trên đồ thị gốc).
  3. Chạy Dijkstra từ t trên đồ thị gốc để tính khoảng cách từ t đến mọi đỉnh (dist_t_inv).

Sau đó, duyệt qua từng cặp cạnh đề xuất (x, y) với trọng số q:

  • Cập nhật kết quả: min(ans, dist_s[x] + q + dist_t_inv[y]).
  • Cập nhật kết quả: min(ans, dist_s[y] + q + dist_t_inv[x]).

Lưu ý: dist_t_inv ở đây là khoảng cách từ t đến các đỉnh, cần dùng cho trường hợp đi s -> ... -> y -> x -> ... -> t (nếu dist_s[y] là s đến y, và dist_t_inv[x] là t đến x (suy ra x đến t là dist_t[x]). Để chuẩn hóa:

  • d1[u]: khoảng cách từ s đến u.
  • d2[u]: khoảng cách từ u đến t.
  • d3[u]: khoảng cách từ t đến u.

Công thức:

  • s -> x -> y -> t: d1[x] + q + d2[y] (trong đó d2[y] là khoảng cách từ y đến t).
  • s -> y -> x -> t: d1[y] + q + d2[x].

Cần 2 lần Dijkstra: Từ s (đồ thị gốc) và từ t (đồ thị ngược).

Cách Dijkstra 2 lần (Tiết kiệm)
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
const long long INF = 1e18;

struct Edge { int v, w; };

int n, m, k, s, t;
vector<Edge> adj[N], rev[N];
int X[305], Y[305], Q[305];
long long d_s[N], d_t[N];

void dijkstra(int start, long long dist[], const vector<Edge> graph[]) {
    for (int i = 1; i <= n; ++i) dist[i] = INF;
    dist[start] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k >> s >> t;
    for (int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        rev[v].push_back({u, c});
    }
    for (int i = 0; i < k; ++i) {
        cin >> X[i] >> Y[i] >> Q[i];
    }

    // 1. Khoảng cách từ s đến mọi đỉnh
    dijkstra(s, d_s, adj);

    // 2. Khoảng cách từ mọi đỉnh đến t (chạy Dijkstra từ t trên đồ thị ngược)
    dijkstra(t, d_t, rev);

    long long ans = d_s[t];

    for (int i = 0; i < k; ++i) {
        int u = X[i], v = Y[i];
        long long w = Q[i];

        // Case 1: s -> u -> v -> t
        if (d_s[u] != INF && d_t[v] != INF) {
            ans = min(ans, d_s[u] + w + d_t[v]);
        }

        // Case 2: s -> v -> u -> t
        if (d_s[v] != INF && d_t[u] != INF) {
            ans = min(ans, d_s[v] + w + d_t[u]);
        }
    }

    if (ans >= INF) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}
  • Time Complexity: O((M + K) log N)
  • Space Complexity: O(M + N)

Đây là cách tối ưu nhất. Giả sử ta chọn cạnh (x, y) với chi phí q. Đường đi ngắn nhất mới sẽ là:

  1. s -> x -> y -> t: Chi phí là (khoảng cách từ s đến x) + q + (khoảng cách từ y đến t).
  2. s -> y -> x -> t: Chi phí là (khoảng cách từ s đến y) + q + (khoảng cách từ x đến t).

Ta chỉ cần thực hiện 2 lần chạy Dijkstra:

  1. dijkstra(s, adj): tính d_s[u] là khoảng cách từ s đến u.
  2. dijkstra(t, rev): tính d_t[u] là khoảng cách từ u đến t (bằng cách chạy Dijkstra từ t trên đồ thị ngược).

Lưu ý: d_t[u] trong code là khoảng cách từ u đến t. Giả sử:

  • d_s[u]: s -> u
  • d_t[u]: u -> t

Thì:

  • Đường 1: s -> x -> y -> t = d_s[x] + q + d_t[y].
  • Đường 2: s -> y -> x -> t = d_s[y] + q + d_t[x].

Cách này loại bỏ hoàn toàn lần Dijkstra thứ 3 bằng cách nhận thấy rằng ta chỉ cần khoảng cách từ s đến các đầu mút và từ các đầu mút đến t. Ta không cần khoảng cách giữa các đầu mút với nhau vì ta không được dùng thêm cạnh đề xuất nào khác ở giữa (hoặc nếu dùng, nó sẽ được xử lý ở cặp cạnh đề xuất khác).

Cách Dijkstra với chi phí thay đổi (State-space Dijkstra)
// Pseudo-code for logic, not full
// Idea: Add virtual edges dynamically

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

const int N = 10005;
const long long INF = 1e18;

struct Edge { int v, w; };
int n, m, k, s, t;
vector<Edge> adj[N];
int X[N], Y[N], Q[N];
long long dist[N][2]; // dist[u][0]: chưa dùng cạnh đề xuất, dist[u][1]: đã dùng

void solve() {
    // Build graph
    // Dijkstra
    // Priority queue stores {cost, u, used}
    // If !used:
    //   - Add normal edges to {v, 0}
    //   - For each proposal edge connected to u (u is X[i] or Y[i]), add to {other, 1}
    // If used:
    //   - Add normal edges to {v, 1}
    //   - Do not add proposal edges
}

int main() {
    // Input reading
    // solve();
    return 0;
}
  • Time Complexity: O((M + K) log N)
  • Space Complexity: O(M + N)

Một cách tiếp cận khác (ít phổ biến hơn nhưng đúng) là sử dụng Dijkstra trên đồ thị có trạng thái.

Ta định nghĩa trạng thái cho mỗi nút u:

  • dist[u][0]: Khoảng cách ngắn nhất từ s đến u mà chưa sử dụng bất kỳ cạnh đề xuất nào.
  • dist[u][1]: Khoảng cách ngắn nhất từ s đến u mà đã sử dụng chính xác một cạnh đề xuất.

Luồng Dijkstra:

  1. Khởi tạo dist[s][0] = 0, các giá trị khác là vô cùng.
  2. Khi ở trạng thái u và chưa dùng cạnh đề xuất (used = 0):
    • Duyệt qua các cạnh thường u -> v: cập nhật dist[v][0].
    • Duyệt qua các cạnh đề xuất liên quan đến u (ví dụ (u, v) trong danh sách): cập nhật dist[v][1] với chi phí dist[u][0] + q.
  3. Khi ở trạng thái u và đã dùng cạnh đề xuất (used = 1):
    • Duyệt qua các cạnh thường u -> v: cập nhật dist[v][1].

Đáp án là min(dist[t][0], dist[t][1]).

Cách này đúng nhưng yêu cầu xử lý ma trận kề hoặc danh sách kề đặc biệt cho cạnh đề xuất để truy vấn nhanh. Do k nhỏ, có thể tối ưu bằng cách lưu cạnh đề xuất riêng.

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

Cách tiếp cận Time Space Tên
1 O(K + (M + K) log N) O(M + N) Dijkstra 3 lần (Đếm đường đi qua cạnh đề xuất)
2 O((M + K) log N) O(M + N) Dijkstra 2 lần (Tiết kiệm)
3 O((M + K) log N) O(M + N) Dijkstra với chi phí thay đổi (State-space Dijkstra)

Bài học kinh nghiệm

  • Bài toán có thể biến đổi thành bài toán tìm min của các đường đi có dạng: đường đi ban đầu + cạnh đề xuất + đường đi ban đầu.
  • Việc chỉ có k cạnh đề xuất cho phép ta duyệt qua từng cặp một thay vì phải xử lý phức tạp trong Dijkstra.

Lỗi thường gặp

  • Quên xử lý trường hợp đồ thị có khuyên (cycle) hoặc đường đi không tồn tại (giá trị vô cùng).
  • Sử dụng biến int thay vì long long dẫn đến tràn số (overflow).
  • Chạy Dijkstra trên đồ thị không liên thông, dẫn đến lỗi truy cập mảng nếu không kiểm tra điều kiện.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.