Hiểu bài toán

Bài toán yêu cầu tìm độ dài đường đi ngắn nhất từ nút 1 (nhà) đến nút N (trường) trong đồ thị có hướng một phần (có cả đường một chiều và hai chiều) với trọng số dương. Đồng thời, đếm số lượng đường đi ngắn nhất đó. Giới hạn N ≤ 5000, M ≤ 20000.

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

Cách Dijkstra đếm đường đi (Cơ bản)

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

const long long N = 5005;
const long long INF = 1e18;

int n, m;
vector<pair<int, int>> adj[N];
long long dist[N];
long long ways[N];

void dijkstra() {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    ways[1] = 1;

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

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                ways[v] = ways[u];
                pq.push({dist[v], v});
            } else if (dist[v] == dist[u] + w) {
                ways[v] += ways[u];
            }
        }
    }
}

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

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

    dijkstra();

    if (dist[n] == INF) {
        cout << "-1 0" << endl;
    } else {
        cout << dist[n] << " " << ways[n] << endl;
    }

    return 0;
}

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

Đây là thuật toán Dijkstra chuẩn để tìm đường đi ngắn nhất. Để đếm số đường đi, ta duy trì thêm mảng ways[u] là số đường đi ngắn nhất từ nguồn đến u. Khi tìm thấy đường đi ngắn hơn (relaxation), ta cập nhật khoảng cách và số đường đi (bằng số đường đi của nút cha). Khi tìm thấy đường đi có cùng độ dài, ta cộng dồn số đường đi của nút cha vào nút hiện tại. Lưu ý: Lệnh continue sau khi pop từ priority queue là bắt buộc để đảm bảo độ phức tạp và tính chính xác.

Cách Optimized Dijkstra

// Giống Approach 1, tối ưu nhẹ về khai báo biến

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

Các giải pháp nộp vào (vd: vudinhlong, trungnghia032024) sử dụng cùng logic cơ bản là Dijkstra. Cấu trúc dữ liệu ưu tiên (Priority Queue) lưu cặp (khoảng cách, nút). Logic đếm đường đi được xử lý ngay trong bước relax của Dijkstra. Đây là phương pháp tối ưu cho đồ thị thưa (M nhỏ hơn nhiều so với N^2).

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

Bài học kinh nghiệm

• Sử dụng Dijkstra với hàng đợi ưu tiên (min-heap) là hiệu quả nhất cho đồ thị trọng số dương.
• Biến phụ ways[] để đếm đường đi phải được cập nhật trong cả 2 trường hợp: tìm thấy đường ngắn hơn (gán lại) hoặc tìm thấy đường bằng nhau (cộng dồn).
• Cần kiểm tra điều kiện if (d > dist[u]) continue; để tránh xử lý các node đã được tối ưu hóa trước đó.

Lỗi thường gặp

• Quên xử lý trường hợp đồ thị không liên thông (nút N không thể đến được), mặc dù đề bài không yêu cầu output cụ thể cho trường hợp này, nhưng thường cần in ra -1 hoặc 0.
• Sử dụng biến long long cho khoảng cách và số đường đi vì số đường đi có thể rất lớn (đề bài cho phép lên tới 2^63 - 1).
• Lỗi logic khi cập nhật số đường đi: nếu chỉ cập nhật ways[v] = ways[u] mà không xử lý đúng trường hợp có nhiều đường đi ngắn nhất đến u.