fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define el '\n'
  3. #define FNAME "NAME"
  4. #define allof(x) x.begin(),x.end()
  5. #define mset(x) memset(x,0,sizeof(x))
  6. typedef long long ll;
  7. using namespace std;
  8. const long long MOD = (long long) 1e9+7;
  9. void setup(){
  10.     ios_base::sync_with_stdio(0);
  11.     cin.tie(0);cout.tie(0);
  12. 	if (fopen(FNAME".inp","r")) {
  13. 		freopen(FNAME".inp","r",stdin);
  14. 		freopen(FNAME".out","w",stdout);
  15. 	}
  16. }
  17.  
  18. void timer(){
  19.     cerr << "Time run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
  20. }
  21.  
  22. const int MAXN= 5005;
  23. const double INF= DBL_MAX;
  24. typedef pair<double, int> P;
  25. struct Cordinate{
  26.     int x,y;
  27. } oxy[MAXN];
  28.  
  29. double matrix[MAXN][MAXN];
  30.  
  31. int visited[MAXN];
  32.  
  33. double caldistancia(Cordinate &a, Cordinate &b){
  34.     double res= sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
  35.     return res;
  36. }
  37.  
  38. // double Prim(int n){
  39. //     priority_queue<P, vector<P>, greater<P>> pq;
  40. //     pq.push({0.0,1});
  41. //     double cost=0.0;
  42. //     while (!pq.empty()){
  43. //         double w= pq.top().first;
  44. //         int u= pq.top().second;
  45. //         pq.pop();
  46. //         if (visited[u]) continue;
  47. //         visited[u]=1;
  48. //         cost+= w;
  49.  
  50. //         for (int v=1;v<=n;v++){
  51. //             if (!visited[v]){
  52. //                 double we= matrix[u][v];
  53. //                 pq.push({we,v});
  54. //             }
  55. //         }
  56. //     }
  57. //     return cost;
  58. // }
  59.  
  60. double PrimNew(int n){
  61.     double d[MAXN];
  62.     double res=0.0;
  63.     fill(d+1,d+n+1,INF);
  64.     d[1]=0;
  65.     visited[1]=1;
  66.     int nE=0;
  67.     while (1){
  68.         int u=0;
  69.         for (int i=1;i<=n;i++){
  70.             if (!visited[i] and d[i]<d[u]) u=i;
  71.         }
  72.         if (!u) break;
  73.         visited[u]=1;
  74.         res+= d[u];
  75.         nE++;
  76.         for (int v=1;v<=n;v++){
  77.             if (!visited[v] and d[v]> matrix[u][v]){
  78.                 d[v]=matrix[u][v];
  79.             }
  80.         }
  81.     }
  82.     if (nE < n-1) return 0.0;
  83.     return res;
  84. }
  85.  
  86. int main() {
  87.     setup();
  88.     int n;
  89.     cin>>n;
  90.     mset(visited);
  91.     for (int i=1;i<=n;i++){
  92.         cin>>oxy[i].x>>oxy[i].y;
  93.     }
  94.     int m;
  95.     cin>>m;
  96.     for (int i=1;i<=n;i++){
  97.         for (int j=1;j<=n;j++){
  98.             if (i!=j){
  99.                 matrix[i][j]=caldistancia(oxy[i],oxy[j]);
  100.             }
  101.             else{
  102.                 matrix[i][j]=0.0;
  103.             }
  104.         }
  105.     }
  106.     for (int i=0;i<m;i++){
  107.         int u,v;
  108.         cin>>u>>v;
  109.         matrix[u][v]=matrix[v][u]=0.0;
  110.     }
  111.     cout<<fixed<<setprecision(2)<<PrimNew(n);
  112. }
  113.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.00
https://ideone.com/qH3s8a
language:
C++14 (gcc 8.3)
created:
14 hours 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!