SHARE
TWEET

Untitled

a guest Mar 26th, 2020 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #define INF 99999999999999
  7. using namespace std;
  8.  
  9. double min = INF;
  10.  
  11. struct Point
  12. {
  13.     int x;
  14.     int y;
  15. };
  16.  
  17.  
  18. double GetWeight(Point a, Point b)
  19. {
  20.     return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
  21. }
  22.  
  23. bool NotColored(vector <int>& Marked, int& Vertex)
  24. {
  25.     for (int i = 0; i < Marked.size(); ++i)
  26.     {
  27.         if (Marked[i] == Vertex)
  28.             return false;
  29.         else
  30.             return true;
  31.     }
  32. }
  33.  
  34. void MST(vector<int>& Marked, vector<double>& Distance, vector<vector<double>>& Graph, int& V)
  35. {
  36.     int index = 0;
  37.     for (int i = 0; i < Marked.size(); ++i)
  38.     {
  39.         for (int j = 0; j < V; ++j)
  40.         {
  41.             if (NotColored(Marked, j) && Graph[Marked[i]][j] < min)
  42.             {
  43.                 min = Graph[Marked[i]][j];
  44.                 index = j;
  45.             }
  46.         }
  47.     }
  48.     Distance[index] = min;
  49.     Marked.push_back(index);
  50.     min = INF;
  51.  
  52.     if (Marked.size() == V)
  53.     {
  54.         int result = 0;
  55.         for (int i = 0; i < V; ++i)
  56.         {
  57.             if (!NotColored(Marked, i))
  58.             result += Distance[i];
  59.         }
  60.         cout.precision(10);
  61.         cout << result;
  62.         exit(0);
  63.     }
  64.     MST(Marked, Distance, Graph, V);
  65.    
  66.    
  67. }
  68.  
  69. int main()
  70. {
  71.     int V, index = 0;
  72.     cin >> V;
  73.     vector <Point> Points(V);
  74.     vector <int> Marked(1);
  75.     vector <double> Distance(V, INF);
  76.     for (int i = 0; i < V; ++i)
  77.         cin >> Points[i].x >> Points[i].y;
  78.     vector<vector<double>> Graph(V, vector <double>(V));
  79.  
  80.     for (int i = 0; i < V; ++i)
  81.         for (int j = 0; j < V; ++j)
  82.             Graph[i][j] = GetWeight(Points[i], Points[j]);
  83.  
  84.     Marked[0] = 0;
  85.    
  86.     for (int i = 1; i < V; ++i)
  87.     {
  88.         if (Graph[0][i] < min)
  89.         {
  90.             min = Graph[0][i];
  91.             index = i;
  92.         }
  93.     }
  94.     Marked.push_back(index);
  95.     Distance[index] = min;
  96.     min = INF;
  97.  
  98.     MST(Marked, Distance, Graph, V);
  99.     return 0;
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top