matistjati

Untitled

Jul 9th, 2026
10
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 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. const double inf = 1e10;
  12. const double DIST_INF = 1e14;
  13.  
  14. pair<double, vi> hungarian(const vector<vector<double>> &a) {
  15. if (a.empty()) return {0, {}};
  16. int n = sz(a) + 1, m = sz(a[0]) + 1;
  17. vector<double> u(n), v(m);
  18. vi p(m), ans(n - 1);
  19. rep(i,1,n) {
  20. p[0] = i;
  21. int j0 = 0; // add "dummy" worker 0
  22. vector<double> dist(m, DIST_INF);
  23. vi pre(m, -1);
  24. vector<bool> done(m + 1);
  25. do { // dijkstra
  26. done[j0] = true;
  27. int i0 = p[j0], j1 = -1;
  28. double delta = DIST_INF;
  29. rep(j,1,m) if (!done[j]) {
  30. double cur = a[i0 - 1][j - 1] - u[i0] - v[j];
  31. if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
  32. if (dist[j] < delta) delta = dist[j], j1 = j;
  33. }
  34. rep(j,0,m) {
  35. if (done[j]) u[p[j]] += delta, v[j] -= delta;
  36. else dist[j] -= delta;
  37. }
  38. j0 = j1;
  39. } while (p[j0]);
  40. while (j0) { // update alternating path
  41. int j1 = pre[j0];
  42. p[j0] = p[j1], j0 = j1;
  43. }
  44. }
  45. rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1;
  46. return {-v[0], ans}; // min cost
  47. }
  48.  
  49. int main() {
  50. cin.tie(0)->sync_with_stdio(0);
  51. cin.exceptions(cin.failbit);
  52.  
  53. ll n, s, t, q;
  54. cin >> n >> s >> t >> q;
  55. q *= q;
  56.  
  57. vector<vector<double>> cost(t, vector<double>(s, inf));
  58. vector<pii> pos;
  59. vi height;
  60. rep(i, 0, n) {
  61. int x, y, h;
  62. cin >> x >> y >> h;
  63. pos.emplace_back(x, y);
  64. height.push_back(h);
  65. }
  66. vi istown(n);
  67. vi is_spring(n);
  68. vi spring_ind(n);
  69. int ind = 0;
  70. rep(i, 0, s) {
  71. int spr_ind;
  72. cin >> spr_ind;
  73. spr_ind--;
  74. is_spring[spr_ind] = 1;
  75. spring_ind[spr_ind] = ind++;
  76. }
  77. rep(i, 0, t) {
  78. int town_ind;
  79. cin >> town_ind;
  80. town_ind--;
  81. istown[town_ind] = 1;
  82. }
  83.  
  84. ind = 0;
  85. rep(i, 0, n) {
  86. if (istown[i]) {
  87. priority_queue<pair<double, int>> pq;
  88. vi vis(n);
  89. pq.emplace(0, i);
  90. while (pq.size()) {
  91. double d;
  92. int u;
  93. tie(d, u) = pq.top();
  94. pq.pop();
  95.  
  96. if (vis[u]) continue;
  97. vis[u] = 1;
  98. if (is_spring[u]) cost[ind][spring_ind[u]] = -d;
  99.  
  100. rep(j, 0, n) {
  101. if (height[u] >= height[j]) continue;
  102. double dist = pow(pos[u].first - pos[j].first, 2) + pow(pos[u].second - pos[j].second, 2) + pow(height[u] - height[j], 2);
  103. if (dist > q) continue;
  104. pq.emplace(d - sqrt(dist), j);
  105. }
  106. }
  107. ind++;
  108. }
  109. }
  110.  
  111. double c = hungarian(cost).first;
  112. if (c >= inf) cout << "IMPOSSIBLE";
  113. else cout << fixed << setprecision(15) << c;
  114. }
  115.  
Advertisement
Add Comment
Please, Sign In to add comment