fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll MAX = 6676;
  5. #define mod 1000000007
  6. #define EPS 1e-2
  7. ll A[6676][10];
  8. bool visited[MAX];
  9. ll n,p;
  10. long double dis(ll i,ll j)
  11. {
  12.     return ((long double)sqrt((long double)(A[i][0]-A[j][0])*(A[i][0]-A[j][0])+(A[i][1]-A[j][1])*(A[i][1]-A[j][1])));
  13. }
  14. long double mn[6676];
  15. long double prim(long long int x)
  16. {
  17.     long double mincost=0LL;
  18.     for(ll i=1;i<=n;i++)
  19.     {
  20.         visited[i]=false;
  21.         mn[i]=5000;
  22.     }
  23.     visited[1]=true;
  24.     for(ll i=1;i<=n;i++)
  25.     {
  26.         if(visited[i])
  27.             continue;
  28.         if(dis(1,i)+EPS<mn[i])
  29.             mn[i]=dis(1,i);
  30.     }
  31.     while(1)
  32.     {
  33.         long double mn1=5000;
  34.         ll ind=-1;
  35.         for(ll i=1;i<=n;i++)
  36.         {
  37.             if(!visited[i]&&mn[i]+EPS<mn1)
  38.             {
  39.                 mn1=mn[i];
  40.                 ind=i;
  41.             }
  42.         }
  43.         if(mn1==5000)
  44.             break;
  45.         mincost+=(mn1*p);
  46.         mincost=ceil(mincost);
  47.         if(mincost+EPS>=mod)
  48.             mincost-=mod;
  49.         visited[ind]=true;
  50.         for(ll i=1;i<=n;i++)
  51.         {
  52.             if(visited[i])
  53.                 continue;
  54.             if(dis(ind,i)+EPS<mn[i])
  55.                 mn[i]=dis(ind,i);
  56.         }
  57.     }
  58.     return mincost;
  59. }
  60. int main()
  61. {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(NULL);
  64.     cout.tie(NULL);
  65.     long long int t,x,i,j;
  66.     long double mincost;
  67.     cin>>t;
  68.     ll z=0;
  69.     while(t--)
  70.     {
  71.         z++;
  72.         cout<<"Scenario #"<<z<<": ";
  73.         cin>>n>>p;
  74.         for(i=1;i<=n;i++)
  75.         {
  76.             cin>>A[i][0]>>A[i][1];
  77.         }
  78.         mincost=prim(1);
  79.         //mincost*=p;
  80.         //if(mincost>=mod)
  81.           //  mincost-=mod;
  82.         cout<<mincost<<"\n";
  83.     }
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
2

4 1

35 46

29 13

44 0

27 17

3 18

18 0

11 17

2 31
stdout
copy 
Scenario #1: 56
Scenario #2: 631
https://ideone.com/0uZeFr
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years 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!