Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cmath>
- #include <vector>
- #include <string>
- #define INF 99999999999999
- using namespace std;
- double min = INF;
- struct Point
- {
- int x;
- int y;
- };
- double GetWeight(Point a, Point b)
- {
- return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
- }
- bool NotColored(vector <int>& Marked, int& Vertex)
- {
- for (int i = 0; i < Marked.size(); ++i)
- {
- if (Marked[i] == Vertex)
- return false;
- else
- return true;
- }
- }
- void MST(vector<int>& Marked, vector<double>& Distance, vector<vector<double>>& Graph, int& V)
- {
- int index = 0;
- for (int i = 0; i < Marked.size(); ++i)
- {
- for (int j = 0; j < V; ++j)
- {
- if (NotColored(Marked, j) && Graph[Marked[i]][j] < min)
- {
- min = Graph[Marked[i]][j];
- index = j;
- }
- }
- }
- Distance[index] = min;
- Marked.push_back(index);
- min = INF;
- if (Marked.size() == V)
- {
- int result = 0;
- for (int i = 0; i < V; ++i)
- {
- if (!NotColored(Marked, i))
- result += Distance[i];
- }
- cout.precision(10);
- cout << result;
- exit(0);
- }
- MST(Marked, Distance, Graph, V);
- }
- int main()
- {
- int V, index = 0;
- cin >> V;
- vector <Point> Points(V);
- vector <int> Marked(1);
- vector <double> Distance(V, INF);
- for (int i = 0; i < V; ++i)
- cin >> Points[i].x >> Points[i].y;
- vector<vector<double>> Graph(V, vector <double>(V));
- for (int i = 0; i < V; ++i)
- for (int j = 0; j < V; ++j)
- Graph[i][j] = GetWeight(Points[i], Points[j]);
- Marked[0] = 0;
- for (int i = 1; i < V; ++i)
- {
- if (Graph[0][i] < min)
- {
- min = Graph[0][i];
- index = i;
- }
- }
- Marked.push_back(index);
- Distance[index] = min;
- min = INF;
- MST(Marked, Distance, Graph, V);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement