fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #define inf 9999999
  6. #define x first
  7. #define y second
  8. using namespace std;
  9.  
  10. pair <int, int> p[3000];
  11.  
  12. int n;
  13.  
  14. int distance(int x1, int y1, int x2, int y2) {
  15. 	return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
  16. }
  17.  
  18. int bellman(int st, int en)
  19. {
  20. 	int dis[3000];
  21. 	memset (dis, inf, sizeof(dis));
  22. 	dis[st] = 0;
  23. 	for (int i = 0; i <= n + 1; i++) {
  24. 		for (int j = 0; j <= n + 1; j++) {
  25. 			int dist = distance(p[i].x, p[i].y, p[j].x, p[j].y);
  26. 			if (dis[i] + dist < dis[j]) {
  27. 				dis[j] = dis[i] + dist;
  28. 			}
  29. 		}
  30. 	}  
  31. 	return dis[en];
  32. } 
  33. int main()
  34. {
  35. 	int t;
  36. 	cin >> t;
  37. 	while (t--) {
  38. 		scanf ("%d", &n);
  39. 		for (int i = 1; i <= n; i++) {
  40. 			scanf ("%d%d", &p[i].x, &p[i].y);
  41. 		}
  42.  
  43. 		scanf ("%d%d", &p[0].x, &p[0].y);
  44. 		scanf ("%d%d", &p[n + 1].x, &p[n + 1].y);
  45. 		printf ("%d\n", bellman(0, n + 1));
  46. 	}
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 3320KB
comments (?)
stdin
copy 
2
6
8 2
4 0
8 0
4 -1
7 -1
6 -2
2 1
9 2
1
0 0
-1 1
1 -1
stdout
copy 
26
4
https://ideone.com/IFzUIx
language:
C++ (gcc 8.3)
created:
10 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!