Chương trình C++ tìm đường đi ngắn nhất qua đỉnh k cho nhiều truy vấn

Cho cây n đỉnh, cạnh có trọng số. q truy vấn (x,y). Tìm độ dài đường đi ngắn nhất từ x đến y đi qua đỉnh k. In kết quả mỗi truy vấn.

Ví dụ

Với n=6, q=3, k=1, cây và truy vấn cho trước, đầu ra 6 11 9.

Giải thuật

Trên cây, đường đi x -> y qua k = dist(x,k) + dist(k,y). DFS từ k tính khoảng cách đến mọi đỉnh (pathTotal). Mỗi truy vấn trả về pathTotal[x] + pathTotal[y].

Mã 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[a]) {
        if (i.first == b) continue;
        pathTotal[i.first] = pathTotal[a] + i.second;
        dfs(i.first, a);
    }
}

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

Đầu vào / Đầu ra

Input: 6, 3, 1, edges, queries
Output: 6 11 9