Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. using namespace std;
  5. const double MAX_INT = 30000;
  6. void prim(vector<pair<int,int>> g, vector<double> &dist, vector<bool> &used, double &sum, int min_ind, int n)
  7. {
  8. int tmp;
  9. for (int k = 1; k <= n; k++) {
  10. used[min_ind] = true;
  11. sum = sum + dist[min_ind];
  12. double min = MAX_INT;
  13. tmp = min_ind;
  14. min_ind = -1;
  15. double way;
  16. for (int j = 1; j <= n; j++) {
  17. if (!used[j]) {
  18. way = sqrt(pow((g[tmp].first - g[j].first), 2) + pow((g[tmp].second - g[j].second), 2));
  19. if (way < dist[j])
  20. dist[j] = way;
  21. if (dist[j] < min) {
  22. min = dist[j];
  23. min_ind = j;
  24. }
  25. }
  26. }
  27. }
  28. }
  29. int main() {
  30. freopen("spantree.in", "r", stdin);
  31. freopen("spantree.out", "w", stdout);
  32. int n;
  33. cin >> n;
  34. vector<pair<int,int>> g(n + 1);
  35. vector<double> dist(n + 1);
  36. vector<bool> used(n + 1, false);
  37. double sum = 0;
  38. for (int i = 1; i <= n; i++) {
  39. cin >> g[i].first >> g[i].second;
  40. dist[i] = MAX_INT;
  41. }
  42. dist[1] = 0;
  43. prim(g, dist, used, sum, 1, n);
  44. cout.precision(6);
  45. cout << fixed << sum;
  46. return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement