Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

读取坐标真的要%lf .......亲身经历 : (

Posted by FAKEGOD at 2018-08-07 11:06:55 on Problem 3625
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
//#define LOCAL

using namespace std;
const double INF = 0x3f3f3f3f3f3f3f3f;

struct NODE
{
    double x,y;
    NODE(int a = 0,int b = 0):x(a),y(b){}
}nodes[1010];

double cost[1010][1010];

double cal_dis(const NODE& a,const NODE& b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int main()
{
#ifdef LOCAL
    freopen("./in.txt","r",stdin);
    freopen("./out.txt","w",stdout);
#endif
    memset(cost,0,sizeof(cost));
    int n,m; scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%lf%lf",&nodes[i].x,&nodes[i].y);
    for(int i = 1;i <= n;i++)
    {
        for(int j = i+1;j <= n;j++)
        {
            cost[i][j] = cost[j][i] = cal_dis(nodes[i],nodes[j]);
        }
    }
    while(m--)
    {
        int x,y; scanf("%d%d",&x,&y);
        cost[x][y] = cost[y][x] = 0;
    }
    //PRIM
    double mincost[1010];
    bool used[1010];
    fill(used,used+n+1,false);
    fill(mincost,mincost+n+1,INF);
    mincost[1] = 0;
    double res = 0;
    while(true)
    {
        int v = -1;
        for(int u = 1;u <= n;u++)
        {
            if(!used[u] && (v == -1 || mincost[u]<mincost[v])) v = u;
        }
        if(v == -1)  break;
        used[v] = true;
        res += mincost[v];
        for(int u = 1; u <= n;u++) mincost[u] = min(mincost[u],cost[v][u]);
    }
    printf("%.2f\n",res);
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator