#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#define INF 9999999
using namespace std;

int S,N;

struct Point{
  int x,y;
};

Point P[505];
double dis[505];

struct XEdge{
   int v;
   double w;
   XEdge(int v_=0,double w_=INF):v(v_),w(w_){}
};

inline double dista( Point p1, Point p2){
    return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(double)(p1.y-p2.y)*(p1.y-p2.y));
}

vector<vector<XEdge> > G(30);


double HeapPrim(const vector<vector<XEdge> > &G,int n)
{
    int i,j,k;
    XEdge xDist(0,0);
    priority_queue<XEdge> pq;
    vector<double> vDist(n);
    vector<int> vUsed(n);
    
    int nDoneNum = 0;
    
    for(i=0;i<n;i++){
      vUsed[i] = 0;
      vDist[i] = INF;
    }
    
    nDoneNum = 0;
    double nTotal = 0;
    
    pq.push(XEdge(0,0));
    
    while(nDoneNum<n&&!pq.empty()){
         do{
            xDist = pq.top(); pq.pop();
         }while(vUsed[xDist.v]==1&&!pq.empty());
         if(vUsed[xDist.v]==0){
            nTotal+=xDist.w;           
           dis[nDoneNum++] = xDist.w;
           vUsed[xDist.v] = 1;
           
           for(i =0;i<G[xDist.v].size();i++){
              int k= G[xDist.v][i].v;
              if(vUsed[k] == 0){
                double w = G[xDist.v][i].w;
                if(vDist[k]>w){
                   vDist[k] = w;
                   pq.push(XEdge(k,w));
                }
              }
           }
         }
    }
    if(nDoneNum<n)
      return -1;
    return nTotal;  
}

bool operator <(const XEdge &e1,const XEdge &e2)
{
  return e1.w>e2.w;
}

int main()
{
    int i,j,t;
    scanf("%d",&t);
 
    
    while(t--){
      scanf("%d %d",&S,&N);                       
    for(i=0;i<N;i++){
      scanf("%d %d",&P[i].x,&P[i].y);
      for(j=0;j<i;j++){
        double d = dista(P[i],P[j]);
        XEdge xDist(0,0);
        xDist.v=i,
        xDist.w=d;
        G[j].push_back(xDist);
        xDist.v=j;
        xDist.w=d;
        G[i].push_back(xDist);
      }
    }
    
    
    HeapPrim(G,N);
    sort(dis+1,dis+N);

    printf("%0.2f\n",dis[N-S]);
    
    }
    return 0;
     
    
}

• Re:请教：Prim+堆 样例没问题，据也行，但是提交WrongAnwer，能给几组测试数24小时等回帖 (11) wyu_adole 2010-08-06 10:17:59
  • Re:请教：Prim+堆 样例没问题，据也行，但是提交WrongAnwer，能给几组测试数24小时等回帖 (29) guojiaqi0000 2010-08-06 12:55:30
• 测试数据 (5392) zegel 2010-08-07 14:17:40
  • Re:测试数据 (7769) luchenqun 2010-10-20 13:59:56