โปรแกรม C++ เพื่อค้นหาผลรวมของเส้นทางต้นทุนที่สั้นที่สุดสำหรับแฝดสามที่ให้มาทั้งหมด

สมมติว่า มี n เมืองและ m ถนนระหว่างเมือง ถนน m มอบให้เราเป็นแถวของถนนที่มีถนนอยู่ในรูปแบบ {aource, destination, weight} ตอนนี้ เรากำหนดแฝดสาม (s, t, k) โดยที่ s, t และ k คือเมือง ตอนนี้เราต้องคำนวณเวลาขั้นต่ำที่จำเป็นในการรับจากเมืองหนึ่งไปยังอีกเมืองหนึ่ง หากต้องการเยี่ยมชม t จาก s สามารถเยี่ยมชมได้เฉพาะเมืองที่อยู่ภายใน 1 ถึง k หากไม่สามารถเข้าถึงเมือง t จาก s เราจะคืนค่า 0 เราต้องคำนวณเวลาต่ำสุดสำหรับแฝดสามทั้งหมด (s, t, k) และพิมพ์ผลรวมของพวกมัน

ดังนั้น หากอินพุตเป็น n =4, m =2, edge ={{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