fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. typedef long long ll;
  5.  
  6. struct spot{
  7. 	int h, w, l;
  8. 	bool r;
  9. } *v;
  10.  
  11. struct state{
  12. 	int x;
  13. 	double dist;
  14. 	state(int n, double d): x(n), dist(d){}
  15. 	bool operator<(const state& other) const
  16. 	{
  17. 		return dist > other.dist;
  18. 	}
  19. };
  20.  
  21. int n, l, w;
  22. vector<state> *edge;
  23.  
  24. double dijkistra(const state s)
  25. {
  26. 	double *cmp = new double[n + 2];
  27. 	memset(cmp, 127, (n + 2) * sizeof(double));
  28. 	priority_queue<state> q;
  29. 	q.push(s);
  30. 	cmp[0] = 0;
  31. 	while(!q.empty())
  32. 	{
  33. 		state i = q.top();
  34. 		q.pop();
  35. 		if(cmp[i.x] == -1)
  36. 			continue;
  37. 		if(i.x == n + 1)
  38. 		{
  39. 			delete[] cmp;
  40. 			return i.dist;
  41. 		}
  42. 		for(state j: edge[i.x])
  43. 			if(cmp[j.x] > j.dist + i.dist)
  44. 			{
  45. 				j.dist += i.dist;
  46. 				cmp[j.x] = j.dist;
  47. 				q.push(j);
  48. 			}
  49. 	}
  50. }
  51.  
  52. double DIST(spot& a, spot& b)
  53. {
  54. 	if(a.r == b.r || a.w + b.w >= w)
  55. 		if(a.l > b.l)
  56. 			return a.l - b.l - b.h;
  57. 		else
  58. 			return b.l - a.l - a.h;
  59. 	else if((a.l <= b.l && a.l + a.h >= b.l) || (b.l <= a.l && b.l + b.h >= a.l))
  60. 		return w - a.w - b.w;
  61. 	else{
  62. 		ll xi, xj, yi, yj;
  63. 		if(a.l > b.l)
  64. 			xi = a.l, xj = b.l + b.h;
  65. 		else
  66. 			xj = b.l, xi = a.l + a.h;
  67. 		yi = a.w;
  68. 		if(a.r)
  69. 			yi = w - yi;
  70. 		yj = b.w;
  71. 		if(b.r)
  72. 			yj = w - yj;
  73. 		return hypot(abs(xi - xj), abs(yi - yj));
  74. 	}
  75. }
  76.  
  77. double dis(spot& a, spot& b) {
  78. 	ll xx, yy;
  79. 	if (a.r == b.r) xx = 0;
  80. 	else {
  81. 		ll x1, x2;
  82. 		if (a.r == 0) x1 = a.w;
  83. 		else x2 = w - a.w;
  84. 		if (b.r == 0)x1 = b.w;
  85. 		else x2 = w - b.w;
  86. 		xx = max(x2 - x1, 0LL);
  87. 	}
  88. 	if (a.l > b.l)
  89. 		yy = max(a.l - (b.l + b.h), 0);
  90. 	else yy = max(b.l - (a.l + a.h), 0);
  91. 	return sqrt(xx * xx + yy * yy);
  92. }
  93.  
  94. int main()
  95. {
  96.     cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);
  97.     freopen("street.in", "r", stdin);
  98.     int t;
  99.     for(cin >> t; t; t--)
  100.     {
  101.     	cin >> n >> l >> w;
  102.     	v = new spot[n];
  103.     	for(int i = 0; i < n; i++)
  104.     		cin >> v[i].h >> v[i].w >> v[i].l >> v[i].r;
  105.     	edge = new vector<state>[n + 2];
  106.     	for(int i = 0; i < n; i++)
  107.     	{
  108.     		edge[0].push_back(state(i + 1, v[i].l));
  109.     		edge[i + 1].push_back(state(n + 1, l - v[i].l - v[i].h));
  110.     		for(int j = i + 1; j < n; j++)
  111.     		{
  112.     			double dist = dis(v[i], v[j]);
  113.     			//double dist = DIST(v[i], v[j]);
  114. 				edge[i + 1].push_back(state(j + 1, dist));
  115. 				edge[j + 1].push_back(state(i + 1, dist));
  116.     		}
  117.     	}
  118.     	delete[] v;
  119.     	cout << fixed << setprecision(6) << dijkistra(state(0, 0)) << endl;
  120.     	delete[] edge;
  121.     }
  122. }
Runtime error #stdin #stdout #stderr 0s 4408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
free(): double free detected in tcache 2
https://ideone.com/PA6oaF
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!