HDU 1875 畅通工程再续

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <queue>
  4 #include <math.h>
  5 using namespace std;
  6 
  7 const int N = 110;
  8 const double inf = 1e9;
  9 double g[N][N];
 10 
 11 struct City{
 12     double dis;
 13     bool vis;
 14 }city[N];
 15 struct Place{
 16     double x;
 17     double y;
 18 }p[N];
 19 struct node{
 20     int loc;
 21     double w;
 22 
 23     bool friend operator<(const node& a,const node& b){
 24         return a.w > b.w;
 25     }
 26 };
 27 priority_queue<node > que;
 28 
 29 void init(int& n){
 30 
 31     for(int i = 1; i <= n; i++){
 32 
 33         city[i].dis = inf;
 34         city[i].vis = 0;
 35         for(int j = 1; j <= n; j++)
 36             if(i == j) g[i][j] = 0;
 37             else g[i][j] = inf;
 38     }
 39 }
 40 
 41 double inline dist(int a,int b){
 42     return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
 43 }
 44 
 45 void get_map(int& n){
 46 
 47     double tmp_d;
 48     for(int i = 1; i <= n; i++)
 49         for(int j = i+1; j <= n; j++){
 50             tmp_d = dist(i,j);
 51             if(tmp_d >= 10 && tmp_d <= 1000)
 52                 g[i][j] = g[j][i] = tmp_d;
 53         }
 54 }
 55 
 56 void prime(double& ans,int& n){
 57 
 58     while(!que.empty()) que.pop();
 59     que.push(node{1,0});
 60     city[1].dis = 0;
 61 
 62     int u;
 63     while(!que.empty()){
 64         u = que.top().loc;
 65         que.pop();
 66         city[u].vis = 1;
 67 
 68         for(int v = 1; v <= n; v++){
 69             if(!city[v].vis && city[v].dis > g[u][v]){
 70                 city[v].dis = g[u][v];
 71                 que.push(node{v,city[v].dis});
 72             }
 73         }
 74     }
 75 
 76     for(int i = 1; i <= n; i++){
 77         if(city[i].dis == inf){
 78             ans = 0;
 79             return;
 80         }
 81         ans += city[i].dis;
 82     }
 83 
 84 }
 85 
 86 int main(){
 87 
 88     int T;
 89     while(~scanf("%d",&T)){
 90 
 91         while(T--){
 92             int n;
 93             scanf("%d",&n);
 94 
 95             init(n);
 96 
 97             for(int i = 1; i <= n; i++)
 98                 scanf("%lf%lf",&p[i].x,&p[i].y);
 99 
100             get_map(n);
101 
102             double ans = 0;
103             prime(ans,n);
104             if(!ans) printf("oh!
");
105             else printf("%.1f
",ans*100);
106         }
107     }
108 
109     return 0;
110 }