Chương trình C ++ để tìm ra tổng các đường dẫn chi phí ngắn nhất cho tất cả các bộ ba đã cho

Giả sử, có n thành phố và m đường giữa các thành phố. M đường được giao cho chúng ta trong một mảng đường mà các đường có định dạng {aource, destination, weight}. Bây giờ, chúng ta xác định một bộ ba (s, t, k) trong đó s, t và k là các thành phố. Bây giờ chúng ta phải tính thời gian tối thiểu cần thiết để đi từ thành phố s đến thành phố t. Để tham quan t từ s, chỉ có thể đến thăm các thành phố trong phạm vi từ 1 đến k. Nếu thành phố t không thể truy cập được từ s, thì chúng ta trả về 0. Chúng ta phải tính thời gian tối thiểu cho tất cả các bộ ba (s, t, k) và in ra tổng của chúng.

Vì vậy, nếu đầu vào là n =4, m =2, các cạnh ={{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}, thì đầu ra sẽ là 63.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

63