P1265-公路修建

小咪咪 2023-06-01 08:55 15阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define pb push_back
     4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
     5 #define INF 100000003
     6 #define ll long long
     7 inline ll read()
     8 {
     9     ll ans = 0;
    10     char ch = getchar(), last = ' ';
    11     while(!isdigit(ch)) last = ch, ch = getchar();
    12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    13     if(last == '-') ans = -ans;
    14     return ans;
    15 }
    16 inline void write(ll x)
    17 {
    18     if(x < 0) x = -x, putchar('-');
    19     if(x >= 10) write(x / 10);
    20     putchar(x % 10 + '0');
    21 }
    22 
    23 double mincost[5003];
    24 bool used[5003];
    25 
    26 int V;
    27 struct P
    28 {
    29     int x;
    30     int y;
    31 };
    32 P a[5003];
    33 double cal(P a,P b)
    34 {
    35     return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
    36 }
    37 double MST()
    38 {
    39     _for(i,1,V+1)
    40     {
    41         mincost[i] = INF;
    42         used[i] = false;
    43     }
    44 
    45     mincost[1] = 0;
    46     double res = 0;
    47 
    48     while(1)
    49     {
    50         int v = -1;
    51         _for(u,1,V+1)
    52         if(!used[u] && (v==-1 || mincost[u] < mincost[v]))
    53             v = u;
    54 
    55         if(v==-1) break;
    56         used[v] = true;
    57         res += mincost[v];
    58 
    59         _for(u,1,V+1)
    60             mincost[u] = min(mincost[u],cal(a[v],a[u]));
    61     }
    62     return res;
    63 }
    64 
    65 int main()
    66 {
    67     V = read();
    68     _for(i,1,V+1)
    69         a[i].x = read(),a[i].y = read();
    70     
    71     printf("%.2lf\n",MST());
    72     return 0;
    73 }

转载于:https://www.cnblogs.com/Asurudo/p/11524256.html

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关题解 luogu P5021 【赛道修建】

题解 luogu P5021 【赛道修建】时间：2019.8.9 20:40 时间：2019.8.12 题目描述 C 城将要举办一系列的赛车比赛。在比赛前，需

今天药忘吃喽~/ 2023年10月09日 09:41/ 0 赞/ 89 阅读

相关 poj 1265 Area

> 题目衔接：[http://poj.org/problem?id=126][http_poj.org_problem_id_126]5 > <table> > <tbo

末蓝、/ 2023年08月17日 17:33/ 0 赞/ 152 阅读

相关洛谷 P1111 修复公路

题目背景 AAA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数NNN，和公路数MMM，公路是双向的

矫情吗；*/ 2023年07月13日 03:27/ 0 赞/ 41 阅读

相关 P1111-修复公路

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

以你之姓@/ 2023年06月01日 08:55/ 0 赞/ 50 阅读

相关 P1265-公路修建

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

小咪咪/ 2023年06月01日 08:55/ 0 赞/ 16 阅读

相关 UESTC 1265-宝贵资源

宝贵资源 [Edit][] Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Jav

悠悠/ 2022年08月19日 13:20/ 0 赞/ 158 阅读

相关 TYVJ P1015 公路乘车 &&洛谷 P1192 台阶问题 Label:dp

题目描述有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式。输入输出格式输入格式：输入文件的仅包含两

- 日理万妓/ 2022年01月09日 07:03/ 0 赞/ 232 阅读

相关城市修建-java

题目描述：有一个城市需要修建，给你N个民居的坐标X,Y，问把这么多民居全都包进城市的话，城市所需最小面积是多少（注意，城市为平行于坐标轴的正方形）输入： 2

太过爱你忘了你带给我的痛/ 2021年11月13日 21:24/ 0 赞/ 270 阅读

相关 CCF 地铁修建

一、试题问题描述　　A市有n个交通枢纽，其中1号和n号非常重要，为了加强运输能力，A市决定在1号到n号枢纽间修建一条地铁。　　地铁由很多段隧道组成，每段隧道

迷南。/ 2021年09月14日 02:16/ 0 赞/ 378 阅读

相关 1265 - B. Beautiful Numbers

[Beautiful Numbers][] 思路：先想想暴力的方法，对于m把从一到m每个数的位置求出来，如果最右边的减最左边的数+1等于m,则说明所有数覆盖的范围刚好是m

痛定思痛。/ 2021年07月17日 02:20/ 0 赞/ 357 阅读