Tìm khoảng cách ngắn nhất giữa hai nút "tốt" (good nodes) trong đồ thị C++

Cho đồ thị vô hướng có trọng số, một số nút được đánh dấu "tốt". Tìm khoảng cách ngắn nhất giữa bất kỳ cặp nào của hai nút tốt khác nhau.

Thuật toán: Chạy Dijkstra từ mỗi nút tốt

• Với mỗi nút tốt i, chạy Dijkstra tìm đường đi ngắn nhất đến các nút khác.
• Dừng sớm khi đã tìm thấy 2 nút tốt (khoảng cách thứ 2 là khoảng cách đến nút tốt gần nhất khác).
• Cập nhật kết quả toàn cục.

Triển khai C++

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

#define N 100005
#define INF 99999999

void add_edge(vector<pair<int,int>> g[], int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
}

int min_dist_good_nodes(vector<pair<int,int>> g[], int n, bool good[]) {
    int res = INF;
    vector<int> dist(n+1), vis(n+1);
    
    for (int i = 1; i <= n; i++) if (good[i]) {
        fill(dist.begin(), dist.end(), INF);
        fill(vis.begin(), vis.end(), 0);
        dist[i] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, i});
        int found = 0;
        
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            if (good[u]) found++;
            if (found == 2) { res = min(res, d); break; }
            if (d > res) break; // pruning
            
            for (auto [v, w] : g[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }
    return res;
}

int main() {
    int n = 5, m = 5;
    vector<pair<int,int>> g[N];
    add_edge(g, 1, 2, 3);
    add_edge(g, 2, 3, 4);
    add_edge(g, 3, 4, 1);
    add_edge(g, 4, 5, 8);
    bool good[N] = {0};
    good[1] = good[3] = good[5] = 1;
    cout << min_dist_good_nodes(g, n, good); // Output: 7
    return 0;
}

Kết quả

7

Giải thích: Cặp (1,3) khoảng cách 7, (3,5) khoảng cách 9, (1,5) khoảng cách 16. Min = 7.

Độ phức tạp: O(k * (M log N)) với k = số nút tốt.