หาระยะทางสั้นที่สุดระหว่าง Good Nodes ใดๆ สองโหนดใน Weighted Graph ด้วย C++

โจทย์: กราฟไม่มีทิศทางมีน้ำหนัก (weighted undirected graph) มี N โหนด M เอจ บางโหนดเป็น "good nodes" หาระยะทางสั้นที่สุดระหว่างคู่ good nodes ใดๆ หนึ่งคู่

ตัวอย่าง: Good nodes = {1, 3, 5} ระยะทาง: 1-3 = 11, 3-5 = 13, 1-5 = 24 → คำตอบ = 11

อัลกอริธึม: Multi-source Dijkstra (รันจากทุก good node)

1. สำหรับแต่ละ good node รัน Dijkstra หาระยะทางสั้นที่สุดไปทุกโหนด
2. ระหว่างรัน หยุดเร็ว (early termination) ถ้า:
   • พบ good node ตัวที่สอง (good == 2)
   • ระยะทางปัจจุบันเกิน best result แล้ว
3. อัปเดต global minimum

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999

void insert_edge(vector<pair<int, int>> graph[], int x, int y, int w) {
    graph[x].push_back({y, w});
    graph[y].push_back({x, w});
}

int get_min_dist(vector<pair<int, int>> graph[], int n, int dist[], int vis[], int good_verts[], int k) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    int result = MAX_VAL;

    for (int i = 1; i <= n; i++) {
        if (!good_verts[i]) continue;
        for (int j = 1; j <= n; j++) {
            dist[j] = MAX_VAL;
            vis[j] = 0;
        }
        dist[i] = 0;
        while (!q.empty()) q.pop();
        q.push({0, i});
        int good = 0;
        while (!q.empty()) {
            int v = q.top().second; q.pop();
            if (vis[v]) continue;
            vis[v] = 1;
            good += good_verts[v];
            if (dist[v] > result) break;
            if (good == 2 && good_verts[v]) {
                result = min(result, dist[v]);
                break;
            }
            for (auto &e : graph[v]) {
                int to = e.first, w = e.second;
                if (dist[v] + w < dist[to]) {
                    dist[to] = dist[v] + w;
                    q.push({dist[to], to});
                }
            }
        }
    }
    return result;
}

int main() {
    int n = 5, m = 5;
    vector<pair<int, int>> graph[N];
    insert_edge(graph, 1, 2, 3);
    insert_edge(graph, 2, 3, 4);
    insert_edge(graph, 3, 4, 1);
    insert_edge(graph, 4, 5, 8);
    int k = 3;
    int good_verts[N] = {}, vis[N], dist[N];
    good_verts[1] = good_verts[3] = good_verts[5] = 1;
    cout << get_min_dist(graph, n, dist, vis, good_verts, k);
}

อินพุท

n=5, edges: (1,2,3) (2,3,4) (3,4,1) (4,5,8), good={1,3,5}

เอาต์พุท

7

หมายเหตุ: โค้ดตัวอย่างมี insert_edge(1,2,3) ซ้ำ 2 ครั้ง และ output 7 ไม่ใช่ 11 ตามคำอธิบาย อาจเป็นตัวอย่างที่ต่างกัน

Complexity

• Time: O(K * (M log N)) โดย K = จำนวน good nodes
• Space: O(N + M)