fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <cmath>
  8. #include <climits>
  9. #include <queue>
  10. #define M make_pair
  11.  
  12. using namespace std;
  13.  
  14. typedef pair<int,int> pii;
  15. const int inf = 1e9;
  16.  
  17. int main(int argc, char *argv[])
  18. {
  19. 	int n, barnX, barnY, lX, lY, i;
  20. 	cin >> n >> barnX >> barnY >> lX >> lY;
  21.  
  22. 	// (X[0], Y[0]) = (lX, lY) i.e. laser source coordinates
  23. 	// (X[n+1], Y[n+1]) = (barnX, barnY)
  24. 	int X[n+2], Y[n+2];
  25.  
  26. 	X[0] = lX;
  27. 	Y[0] = lY;
  28.  
  29. 	for (int i = 1;i <= n;i++) 
  30. 		cin >> X[i] >> Y[i];
  31.  
  32. 	X[n+1]=barnX;
  33. 	Y[n+1]=barnY;
  34.  
  35. 	// (lX, lY) to (barnX, barnY) 
  36. 	priority_queue<pii, vector<pii>, greater<pii> > Q;
  37.  
  38. 	// nodes[i] = no. of nodes in the path 0..i
  39. 	int dist[n+2], nodes[n+2];
  40.  
  41. 	fill(dist, dist + n + 2, inf);
  42. 	fill(nodes, nodes + n + 2, 0);
  43.  
  44. 	dist[0] = 0;
  45.  
  46. 	Q.push(M(0, 0));
  47.  
  48. 	while (!Q.empty())
  49. 	{
  50. 		int u = Q.top().second;
  51. 		Q.pop();
  52. 		for (i = 1;i <= n+1;i++)
  53. 		{
  54. 			if (X[i] == X[u] && dist[i] > dist[u] + abs(X[i] - X[u]))
  55. 			{
  56. 				dist[i] = abs(X[i] - X[u]);
  57. 				Q.push(M(abs(X[i] - X[u]), i));
  58. 				nodes[i] = nodes[u] + 1;
  59. 			}
  60. 			else if (Y[i] == Y[u] && dist[i] > dist[u] + abs(Y[i] - Y[u])) {
  61. 				dist[i] = abs(Y[i] - Y[u]);
  62. 				Q.push(M(abs(Y[i] - Y[u]), i));
  63. 				nodes[i] = nodes[u] + 1;
  64. 			}
  65. 		}
  66. 	}
  67. 	cout << dist[n+1] << ' ' << nodes[n+1] << endl;
  68. 	return 0;
  69. }
  70.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
4 0 0 7 2
3 2
0 2
1 6
3 0
stdout
copy 
0 2
https://ideone.com/yNBa6P
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

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!