C++ প্রোগ্রাম: দিয়ে দেয়া গ্রাফে q কোয়েরির জন্য শর্টেস্ট পাথ কস্ট

মান লিখুন: একটি গ্রাফ দেওয়া আছে যাতে nটি ভের্টেক্স আছে এবং এটি মিনিমালি কানেক্টেড। এজগুলো {source, dest, weight} ফরম্যাটে দেওয়া আছে। q সংখ্যক কোয়েরি আছে যেখানে প্রতিটি কোয়েরি {source, destination} ফরম্যাটে। ভের্টেক্স k-র মাধ্যমে source থেকে destination-এ যাওয়ার শর্টেস্ট কস্ট পাথ বের করতে হবে। প্রতিটি কোয়েরির জন্য পাথ কস্ট প্রিন্ট করতে হবে।

উদাহরণ

যদি ইনপুট হয় 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।

সমাধানের ধাপসমূহ

graph পেয়ার ২ডি অ্যারে (n*n)
pathTotal অ্যারে (আকার n)
dfs(a, b) ফাংশন:
    graph[a]-এর প্রতিটি i এর জন্য:
        যদি i.first == b: continue
        pathTotal[i.first] := pathTotal[a] + i.second
        dfs(i.first, a)

for i := 0 থেকে n-2:
    a := edges[i].first, b := edges[i].second, c := edges[i].third
    a--, b--
    graph[a]-এ (b,c) পুশ, graph[b]-এ (a,c) পুশ
k--
dfs(k, k)
for i := 0 থেকে q-1:
    x := queries[i].first, y := queries[i].second
    x--, y--
    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