Advertisement
Mohammad_Dipu_Sultan

Warmholes SRBD

Aug 26th, 2023 (edited)
1,286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int x2, y2;
  4. int n, ans;
  5. int a[102][5];
  6.  
  7. void warmhole(int x1, int y1, int ind, int cost){
  8.  
  9.     if(ind==n){//If ind is greater than or equal to n, it means all warmholes have been considered.
  10.         cost+=abs(x1-x2)+abs(y1-y2);//calculates the cost to travel from the current point to the destination
  11.         ans=min(ans, cost);
  12.         return;
  13.     }
  14.  
  15.     int c1 = cost+abs(x1-a[ind][0])+abs(y1-a[ind][1])+a[ind][4];//c1 is the cost of moving from the current point to the warmhole's entry point
  16.     int c2 = cost+abs(x1-a[ind][2])+abs(y1-a[ind][3])+a[ind][4];//c2 is the cost of moving from the current point to the warmhole's exit point
  17.  
  18.     if(c1<=c2 and c1<ans){
  19.  
  20.         warmhole(a[ind][2], a[ind][3], ind+1, c1);
  21.     }
  22.     else if(c2<ans){
  23.  
  24.         warmhole(a[ind][0], a[ind][1], ind+1, c2);
  25.     }
  26.     if(cost<ans){
  27.         warmhole(x1, y1, ind+1, cost);//current warmhole is skipped.
  28.     }
  29.  
  30. }
  31.  
  32. int main(){
  33.  
  34.     int t;
  35.     cin >> t;
  36.     while(t--){
  37.  
  38.         int x1, y1;
  39.         cin >> n;
  40.         cin >> x1 >> y1 >> x2 >> y2;
  41.         for(int i=0; i<n; i++){
  42.             cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4];
  43.         }
  44.  
  45.         ans=INT_MAX;
  46.         warmhole(x1, y1, 0, 0);
  47.         cout << ans << endl;
  48.     }
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement