BOJ_algorithm/10021.cpp at master · WHO-A-U/BOJ_algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;
using vvpll = vector<vpll>;
using vvs = vector<vs>;

ll d[2001][2001];
vpii p;
ll getDist(pii a , pii b){
    return (((ll)(a.first-b.first)*(a.first-b.first))+((ll)(a.second-b.second)*(a.second-b.second)));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x,y;
    ll l;
    cin>>n>>l;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        p.emplace_back(x,y);
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]=INF;
        }
    }

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ll dist = getDist(p[i],p[j]);
            if(dist>=l)
                d[i][j] = d[j][i] =  dist;
        }
    }

    bool visit[2001];
    ll cost[2001];
    memset(visit,false,sizeof(visit));

    for(int i=0;i<n;i++){
        cost[i] = INF;
    }

    ll ans=0;
    queue<int> q;

    q.push(0);
    cost[0]=0;
    visit[0]=true;
    bool isFail=false;
    int cnt=n-1;
    while(cnt--){
        int cur = q.front();
        q.pop();
        for(int i=0;i<n;i++){
            ll nextCost =d[cur][i];
            if(!visit[i]&&(nextCost<cost[i])){
                cost[i] = nextCost;
            }
        }

        ll minVal=INF;
        int idx;

        for(int i=0;i<n;i++){
            if(!visit[i]){
                if(minVal>cost[i]){
                    minVal=cost[i];
                    idx=i;
                }
            }
        }


        if(minVal==INF){
            isFail=true;
            break;
        }

        ans+=minVal;
        visit[idx]=true;
        q.push(idx);
    }
    if(isFail){
        cout<<-1;
    }else{
        cout<<ans;
    }


}