matistjati

Untitled

Jul 9th, 2026
6
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  5. #define all(x) begin(x), end(x)
  6. #define sz(x) (int)(x).size()
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<int> vi;
  10.  
  11. template <typename T> pair<T, vector<int>>
  12. weighted_matching(vector<vector<T>> &C) {
  13. int i = sz(C), m = sz(C[0]), c, j, s, r;
  14. vector<T> dist(m), potential(m);
  15. vi row_match(i), col_match(m, -1), cols(m), prev(m);
  16. T d, nd, cost = 0;
  17. for (; i--;) {
  18. rep(c, 0, m) dist[c] = C[i][c], cols[c] = c, prev[c] = i;
  19. for (s = 0;;) {
  20. for (j = s; j < m; j++) if (c = cols[j],
  21. nd = dist[c] - potential[c], j == s || d > nd)
  22. d = nd, swap(cols[s], cols[j]);
  23. if (!~(r = col_match[c = cols[s++]])) break;
  24. rep(j, 0, m) if (dist[j] > (nd = C[r][j] - C[r][c] +
  25. dist[c])) dist[j] = nd, prev[j] = r;
  26. }
  27. for (cost += dist[c]; s--;) j = cols[s],
  28. potential[j] = dist[j] - d;
  29. for (; r != i; swap(c, row_match[r]))
  30. r = col_match[c] = prev[c];
  31. }
  32. return {cost, row_match};
  33. }
  34.  
  35. const double inf = 1e10;
  36. int main() {
  37. cin.tie(0)->sync_with_stdio(0);
  38. cin.exceptions(cin.failbit);
  39.  
  40. ll n, s, t, q;
  41. cin >> n >> s >> t >> q;
  42. q *= q;
  43.  
  44. vector<vector<double>> cost(t, vector<double>(s, inf));
  45. vector<pii> pos;
  46. vi height;
  47. rep(i, 0, n) {
  48. int x, y, h;
  49. cin >> x >> y >> h;
  50. pos.emplace_back(x, y);
  51. height.push_back(h);
  52. }
  53. vi istown(n);
  54. vi is_spring(n);
  55. vi spring_ind(n);
  56. int ind = 0;
  57. rep(i, 0, s) {
  58. int spr_ind;
  59. cin >> spr_ind;
  60. spr_ind--;
  61. is_spring[spr_ind] = 1;
  62. spring_ind[spr_ind] = ind++;
  63. }
  64. rep(i, 0, t) {
  65. int town_ind;
  66. cin >> town_ind;
  67. town_ind--;
  68. istown[town_ind] = 1;
  69. }
  70.  
  71. ind = 0;
  72. rep(i, 0, n) {
  73. if (istown[i]) {
  74. priority_queue<pair<double, int>> pq;
  75. vi vis(n);
  76. pq.emplace(0, i);
  77. while (pq.size()) {
  78. double d;
  79. int u;
  80. tie(d, u) = pq.top();
  81. pq.pop();
  82.  
  83. if (vis[u]) continue;
  84. vis[u] = 1;
  85. if (is_spring[u]) cost[ind][spring_ind[u]] = -d;
  86.  
  87. rep(j, 0, n) {
  88. if (height[u] >= height[j]) continue;
  89. double dist = pow(pos[u].first - pos[j].first, 2) + pow(pos[u].second - pos[j].second, 2) + pow(height[u] - height[j], 2);
  90. if (dist > q) continue;
  91. pq.emplace(d - sqrt(dist), j);
  92. }
  93. }
  94. ind++;
  95. }
  96. }
  97.  
  98. auto [c, _] = weighted_matching(cost);
  99. if (c >= inf) cout << "IMPOSSIBLE";
  100. else cout << fixed << setprecision(15) << c;
  101. }
  102.  
Advertisement
Add Comment
Please, Sign In to add comment