โปรแกรม C++ หาเส้นทางสั้นที่สุดในกราฟต้นไม้สำหรับหลายคำถาม

คำอธิบายปัญหา

สมมติว่าเรามีกราฟ n โหนด เชื่อมต่อขั้นต่ำ (ต้นไม้) ขอบให้ในอาร์เรย์รูปแบบ {ต้นทาง, ปลายทาง, น้ำหนัก} มี q คำถาม แต่ละคำถามรูปแบบ {ต้นทาง, ปลายทาง} ต้องหาเส้นทางสั้นที่สุดจากต้นทางไปปลายทางผ่านโหนด k พิมพ์ค่าใช้จ่ายแต่ละคำถาม

ตัวอย่าง: n = 6, q = 3, k = 1, edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, queries = {{1, 4}, {2, 6}, {2, 5}} ผลลัพธ์คือ 6 11 9

ขั้นตอนการแก้ปัญหา

กำหนดอาร์เรย์ 2D graph ของคู่ ขนาด n*n
กำหนดอาร์เรย์ pathTotal ขนาด n
ฟังก์ชัน dfs(a, b):
    สำหรับค่า i ใน graph[a]:
        ถ้า first ของ i == b: ข้าม
        pathTotal[first ของ i] := pathTotal[a] + second ของ i
        dfs(first ของ i, a)
สำหรับ i := 0 ถึง n-2:
    a := edges[i] ตัวแรก
    b := edges[i] ตัวที่สอง
    c := edges[i] ตัวที่สาม
    ลด a,b ลง 1
    ใส่คู่ (b,c) ลง graph[a]
    ใส่คู่ (a,c) ลง graph[b]
ลด k ลง 1
dfs(k, k)
สำหรับ i := 0 ถึง q-1:
    x := queries[i] ตัวแรก
    y := queries[i] ตัวที่สอง
    ลด x,y ลง 1
    พิมพ์ pathTotal[x] + pathTotal[y]

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

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

vector<vector<pair<int,int>>> graph;
vector<int> pathTotal;
int k;

void dfs(int a, int b){
    for(auto i : graph.at(a)){
        if(i.first == b) continue;
        pathTotal.at(i.first) = pathTotal.at(a) + i.second;
        dfs(i.first,a);
    }
}

void solve(int n, int q, vector<tuple<int, int, int>> edges, vector<pair<int, int>> queries){
    int a, b, c, x, y;
    graph.resize(n);
    pathTotal.resize(n);
    for(int i = 0; i < n - 1; i++){
        a = get<0> (edges[i]);
        b = get<1> (edges[i]);
        c = get<2> (edges[i]);
        a--, b--;
        graph.at(a).push_back(make_pair(b, c));
        graph.at(b).push_back(make_pair(a, c));
    }
    k--;
    dfs(k, k);
    for(int i = 0; i < q; i++){
        x = queries[i].first;
        y = queries[i].second;
        x--, y--;
        cout << pathTotal.at(x) + pathTotal.at(y) << endl;
    }
}

int main() {
    int n = 6, q = 3;
    k = 1;
    vector<tuple<int, int, int>> edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}};
    vector<pair<int, int>> queries = {{1, 4}, {2, 6}, {2, 5}};
    solve(n, q, edges, queries);
    return 0;
}

อินพุต

6, 3, 1, {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, {{1, 4}, {2, 6}, {2, 5}}

เอาต์พุต

6 11 9