Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define rep(i, a, b) for(int i = a; i < (b); ++i)
- #define all(x) begin(x), end(x)
- #define sz(x) (int)(x).size()
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- const double inf = 1e10;
- const double DIST_INF = 1e14;
- pair<double, vi> hungarian(const vector<vector<double>> &a) {
- if (a.empty()) return {0, {}};
- int n = sz(a) + 1, m = sz(a[0]) + 1;
- vector<double> u(n), v(m);
- vi p(m), ans(n - 1);
- rep(i,1,n) {
- p[0] = i;
- int j0 = 0; // add "dummy" worker 0
- vector<double> dist(m, DIST_INF);
- vi pre(m, -1);
- vector<bool> done(m + 1);
- do { // dijkstra
- done[j0] = true;
- int i0 = p[j0], j1 = -1;
- double delta = DIST_INF;
- rep(j,1,m) if (!done[j]) {
- double cur = a[i0 - 1][j - 1] - u[i0] - v[j];
- if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
- if (dist[j] < delta) delta = dist[j], j1 = j;
- }
- rep(j,0,m) {
- if (done[j]) u[p[j]] += delta, v[j] -= delta;
- else dist[j] -= delta;
- }
- j0 = j1;
- } while (p[j0]);
- while (j0) { // update alternating path
- int j1 = pre[j0];
- p[j0] = p[j1], j0 = j1;
- }
- }
- rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1;
- return {-v[0], ans}; // min cost
- }
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- cin.exceptions(cin.failbit);
- ll n, s, t, q;
- cin >> n >> s >> t >> q;
- q *= q;
- vector<vector<double>> cost(t, vector<double>(s, inf));
- vector<pii> pos;
- vi height;
- rep(i, 0, n) {
- int x, y, h;
- cin >> x >> y >> h;
- pos.emplace_back(x, y);
- height.push_back(h);
- }
- vi istown(n);
- vi is_spring(n);
- vi spring_ind(n);
- int ind = 0;
- rep(i, 0, s) {
- int spr_ind;
- cin >> spr_ind;
- spr_ind--;
- is_spring[spr_ind] = 1;
- spring_ind[spr_ind] = ind++;
- }
- rep(i, 0, t) {
- int town_ind;
- cin >> town_ind;
- town_ind--;
- istown[town_ind] = 1;
- }
- ind = 0;
- rep(i, 0, n) {
- if (istown[i]) {
- priority_queue<pair<double, int>> pq;
- vi vis(n);
- pq.emplace(0, i);
- while (pq.size()) {
- double d;
- int u;
- tie(d, u) = pq.top();
- pq.pop();
- if (vis[u]) continue;
- vis[u] = 1;
- if (is_spring[u]) cost[ind][spring_ind[u]] = -d;
- rep(j, 0, n) {
- if (height[u] >= height[j]) continue;
- double dist = pow(pos[u].first - pos[j].first, 2) + pow(pos[u].second - pos[j].second, 2) + pow(height[u] - height[j], 2);
- if (dist > q) continue;
- pq.emplace(d - sqrt(dist), j);
- }
- }
- ind++;
- }
- }
- double c = hungarian(cost).first;
- if (c >= inf) cout << "IMPOSSIBLE";
- else cout << fixed << setprecision(15) << c;
- }
Advertisement
Add Comment
Please, Sign In to add comment