Advertisement
Josif_tepe

Untitled

Oct 24th, 2023
657
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 1e5 + 10;
  6. const int INF = 1e9;
  7. vector<pair<int, double> > graph[maxn];
  8. int n, m;
  9. struct node {
  10.     int idx;
  11.     double cost;
  12.     node () {}
  13.     node(int _idx, double _cost) {
  14.         idx = _idx;
  15.         cost = _cost;
  16.     }
  17.     bool operator < (const node &tmp) const {
  18.         return cost > tmp.cost;
  19.     }
  20. };
  21.  
  22. double prim() {
  23.     priority_queue<node> pq;
  24.     pq.push(node(0, 0));
  25.     vector<double> dist(n, INF);
  26.     vector<bool> visited(n, false);
  27.     dist[0] = 0;
  28.     double mst = 0;
  29.     while(!pq.empty()) {
  30.         node c = pq.top();
  31.         pq.pop();
  32.        
  33.         if(visited[c.idx]) continue;
  34.         visited[c.idx] = true;
  35.        
  36.         mst += c.cost;
  37.         for(int i = 0; i < (int) graph[c.idx].size(); i++) {
  38.             int neighbour = graph[c.idx][i].first;
  39.             double weight = graph[c.idx][i].second;
  40.             if(!visited[neighbour] and weight < dist[neighbour]) {
  41.                 pq.push(node(neighbour, weight));
  42.                 dist[neighbour] = weight;
  43.             }
  44.         }
  45.     }
  46.     return mst;
  47. }
  48. int main() {
  49.     int t;
  50.     cin >> t;
  51.    
  52.     while(t--) {
  53.         cin >> n;
  54.         vector<pair<double, double> > v;
  55.         for(int i = 0; i < n; i++) {
  56.             graph[i].clear();
  57.             double a, b;
  58.             cin >> a >> b;
  59.             v.push_back(make_pair(a, b));
  60.         }
  61.         for(int i = 0; i < n; i++) {
  62.             for(int j = 0; j < n; j++) {
  63.                 if(i != j) {
  64.                     double dist = sqrt((v[i].first - v[j].first) * (v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second));
  65.                     graph[i].push_back(make_pair(j, dist));
  66.                 }
  67.             }
  68.         }
  69.         printf("%.3lf\n", prim());
  70.  
  71.     }
  72.     return 0;
  73. }
  74.  
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement