글 읽기 - long double을 사용해도 9%에서 틀립니다

tjrcjf410 3년 전 0

간단히 브루스칼로 풀었는데 어떤게 틀린 것인지 알려주시기 바랍니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int m;
int p[1001];
int find(int x){
    if(x==p[x]) return x;
    else return p[x]=find(p[x]);
}
int unions(int x, int y){
    x=find(x);
    y=find(y);
    if(x==y) return 0;
    if(x<y) p[y]=x;
    if(x>y) p[x]=y;
    return 1;
}
pair<int,int> arr[1001];
vector<pair<double,pair<int,int>>> line;
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>arr[i].first;
        cin>>arr[i].second;
        p[i]=i;
    }
    long double sum=0;
    int cnt=0;
    for(int i=1; i<=m; i++){
        int a,b;
        cin>>a>>b;
        cnt++;
        unions(a,b);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) continue;
            int dx=arr[i].first- arr[j].first;
            int dy=arr[i].second- arr[j].second;
            long long db = dx*dx+ dy*dy;
            long double w = sqrt(db);
            line.push_back(make_pair(w,make_pair(i,j)));
        }
    }
    sort(line.begin(), line.end());
    int len = line.size();
    for(int i=0; i<len; i++){
        long double w = line[i].first;
        int a = line[i].second.first;
        int b = line[i].second.second;
        if(unions(a,b)){
            sum+=w;
            cnt++;
        }
        if(cnt==n-1){
            printf("%.2lf",sum);
            return 0;
        }
    }
}

blueapple99 3년 전 0

44번째 줄에서 dx와 dy가 1000000이라면 제곱했을때에 int의 범위를 초과하므로 문제가 발생합니다.

dx,dy를 long long 형으로 선언하시면 될겁니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

long double을 사용해도 9%에서 틀립니다

tjrcjf410 3년 전 0

blueapple99 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말