ধরুন, শহরের মধ্যে n শহর এবং m রাস্তা আছে। m রাস্তাগুলি আমাদেরকে রাস্তাগুলির একটি বিন্যাসে দেওয়া হয়েছে যেখানে রাস্তাগুলি বিন্যাসে রয়েছে {aource, destination, weight}৷ এখন, আমরা একটি ট্রিপলেট (s, t, k) সংজ্ঞায়িত করি যেখানে s, t, এবং k হল শহর। এখন আমাদেরকে শহর থেকে শহরে যেতে ন্যূনতম সময় গণনা করতে হবে। s থেকে t পরিদর্শন করতে, শুধুমাত্র 1 থেকে k এর মধ্যে থাকা শহরগুলি পরিদর্শন করা যেতে পারে। যদি সিটি টি s থেকে পৌঁছানো যায় না, তাহলে আমরা 0 ফেরত দিই। আমাদের সমস্ত ট্রিপলেটের (s, t, k) জন্য সর্বনিম্ন সময় গণনা করতে হবে এবং তাদের যোগফল প্রিন্ট করতে হবে।
সুতরাং, যদি ইনপুটটি n =4, m =2, edges ={{1, 2, 5}, {2, 3, 4}, {3, 4, 3}} এর মত হয়, তাহলে আউটপুট হবে 63।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one 2D array dvec initialized with value infinity for initialize i := 0, when i < n, update (increase i by 1), do: dvec[i, i] := 0 for initialize i := 0, when i < m, update (increase i by 1), do: a := first value of (edges[i]) b := second value of (edges[i]) c := third value of (edges[i]) decrease a and b by 1 dvec[a, b] := c res := 0 for initialize k := 0, when k < n, update (increase k by 1), do: for initialize i := 0, when i < n, update (increase i by 1), do: for initialize j := 0, when j < n, update (increase j by 1), do: dvec[i, j] := minimum of (dvec[i, j] and dvec[i, k] + dvec[k, j]) if dvec[i, j] is not equal to infinity, then: res := res + dvec[i, j] print(res)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; void solve(int n, int m, vector<tuple<int, int, int>> edges){ vector<vector<int>> dvec(n, vector<int>(n, INF)); for(int i = 0; i < n; i++) dvec[i][i] = 0; for(int i = 0; i < m; i++) { int a = get<0> (edges[i]); int b = get<1> (edges[i]); int c = get<2> (edges[i]); a--; b--; dvec[a][b] = c; } int res = 0; for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { dvec[i][j] = min(dvec[i][j], dvec[i][k]+dvec[k][j]); if(dvec[i][j] != INF) res += dvec[i][j]; } } } cout << res << endl; } int main() { int n = 4, m = 2; vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}; solve(n, m, edges); return 0; }
ইনপুট
4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}
আউটপুট
63