fork download
copy 
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. int SX;
  6. int SY;
  7. int TX;
  8. int TY;
  9.  
  10.  
  11. // Since the wormhole is biderctional the two entrance points are stored in (WSX, WSY) ans (WDX , WDY)
  12. // WP helps in tracking which entrance point was used. WSX or WSY is represnted using a 0 in WP and WDX and WDY is represented using a 1
  13.  
  14. int WSX[100];
  15. int WSY[100];
  16. int WDX[100];
  17. int WDY[100];
  18. int WC[100];
  19. int WP[100]; // Helps in tracking which entrance point was used
  20. int N;
  21.  
  22.  
  23. int dist(int a, int b)
  24. {
  25.     int ele = a - b;
  26.  
  27.     if(ele < 0)
  28.         return -ele;
  29.  
  30.     return ele;
  31. }
  32.  
  33.  
  34. void greed(int * visitc, bool * choosen)
  35. {
  36.  
  37.         int mini = 99999999;
  38.         int node = -1;
  39.  
  40.        for(int i = 0; i <= N; ++i)
  41.        {
  42.             if(choosen[i] == false && mini > visitc[i])
  43.             {
  44.                 mini = visitc[i];
  45.                 node = i;
  46.             }
  47.         }
  48.  
  49.  
  50.         if(node == N)
  51.             return;
  52.  
  53.  
  54.        choosen[node] = true;
  55.  
  56.  
  57.  
  58.         for(int i = 0; i <= N; ++i)
  59.         {
  60.             if(i == node || choosen[i] == true)
  61.                 continue;
  62.  
  63.             int temp0;
  64.  
  65.             if(WP[node] == 0)
  66.                 temp0 += ( dist(WSX[i], WDX[node]) + dist(WSY[i], WDY[node]) );
  67.  
  68.             else
  69.                  temp0 += ( dist(WSX[i], WSX[node]) + dist(WSY[i], WSY[node]) );
  70.  
  71.  
  72.             int temp1;
  73.  
  74.             if(WP[node] == 0)
  75.                 temp1 += ( dist(WDX[i], WDX[node]) + dist(WDY[i], WDY[node]) );
  76.  
  77.             else
  78.                  temp1 += ( dist(WDX[i], WSX[node]) + dist(WDY[i], WSY[node]) );
  79.  
  80.             int z;
  81.             int temp;
  82.  
  83.              if(temp0 < temp1)
  84.              {
  85.                  temp = temp0;
  86.                  z = 0;
  87.              }
  88.  
  89.              else
  90.              {
  91.                  temp = temp1;
  92.                  z = 1;
  93.              }
  94.  
  95.              temp += WC[i];
  96.  
  97.             if(visitc[i] > visitc[node] + temp)
  98.             {
  99.                 visitc[i] = visitc[node] + temp;
  100.                 WP[i] = z;
  101.             }
  102.  
  103.         }
  104. }
  105.  
  106.  
  107. int main()
  108. {
  109.  
  110.     cin>>SX>>SY;
  111.     cin>>TX>>TY;
  112.  
  113.     cin>>N;
  114.  
  115.     for(int i = 0; i < N; ++i)
  116.     {
  117.  
  118.         cin>>WSX[i]>>WSY[i];
  119.         cin>>WDX[i]>>WDY[i];
  120.         cin>>WC[i];
  121.     }
  122.  
  123.  
  124.     int visitc[N + 1];
  125.     bool choosen[N + 1];
  126.  
  127.     int ans = (dist(SX, TX) + dist(SY, TY));
  128.  
  129.     visitc[N] = ans;
  130.  
  131.     for(int i = 0; i < N; ++i)
  132.     {
  133.         choosen[i] = false;
  134.  
  135.         int o1 = (dist(SX, WSX[i]) + dist(SY, WSY[i]));
  136.         int o2 = (dist(SX, WDX[i]) + dist(SY, WDY[i]));
  137.  
  138.         visitc[i] = WC[i];
  139.  
  140.         if(o1 < o2)
  141.         {
  142.             WP[i] = 0;
  143.             visitc[i] += o1;
  144.         }
  145.  
  146.        else
  147.        {
  148.              WP[i] = 1;
  149.              visitc[i] += o2;
  150.        }
  151.  
  152.     }
  153.  
  154.  
  155.  
  156.     greed(visitc, choosen);
  157.  
  158.     cout<<visitc[N]<<endl;
  159.  
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0s 4288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ICCdc5
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!