Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <bitset>
- #include <iomanip>
- #include <cmath>
- #include <queue>
- #include <algorithm>
- #define pb push_back
- #define mp make_pair
- #include <iostream>
- #include <queue>
- #include <map>
- #include <vector>
- #include <string>
- #define ll long long
- using namespace std;
- bool taken[2005][2005];
- vector<pair<int,int> > g;
- priority_queue< vector<int>, vector<vector<int> >, greater<vector<int> > > pq;
- int x, c;
- void process(int a, int b) {
- taken[a][b] = true;
- for (int i=0; i < g.size(); i++) {
- pair<int, int> pr = g[i];
- int dist = (a - pr.first)*(a-pr.first) + (b-pr.second)*(b-pr.second);
- if (!taken[pr.first][pr.second] && dist >= c) {
- vector<int> v;
- v.pb(dist);
- v.pb(pr.first);
- v.pb(pr.second);
- pq.push(v);
- }
- }
- }
- int a, b;
- int main() {
- freopen("irrigation.in", "r", stdin);
- freopen("irrigation.out", "w", stdout);
- cin >> x >> c;
- for (int i=0; i < x; i++) {
- cin >> a >> b;
- g.pb(mp(a,b));
- }
- int dist = 0;
- process(a, b);
- while (!pq.empty()) {
- vector<int> pr = pq.top();
- pq.pop();
- int x1 = pr[1];
- int y1 = pr[2];
- int c = pr[0];
- if (!taken[x1][y1]) { dist += c; process(x1, y1);}
- }
- cout << dist << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement