fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <bitset>
  6. #include <stdio.h>
  7. #include <math.h>
  8. using namespace std;
  9. typedef std::vector<int> vi;
  10. typedef std::vector<pair<int, int> > vii;
  11. #define FOR(l) for(vi::iterator it=l.begin();it!=l.end();it++)
  12. #define FOR_L(l, s, e) for(vi::iterator it=l.begin()+s;it!=l.end()-e;it++)
  13. //----------Main source code -----------------//
  14. int m, n, x, y, min_d, cur_d, sz;
  15. vii beepers;
  16. bitset<11> visited;
  17. void rcr(pair<int, int> &from){
  18. 	int tmp;
  19. 	if(visited.all()){
  20. 		tmp=cur_d;
  21. 		cur_d+=abs(x-from.first)+abs(y-from.second);
  22. 		if(cur_d<min_d) min_d=cur_d;
  23. 		cur_d=tmp;
  24. 		return;
  25. 	}
  26. 	for(int z=0;z<sz;z++)
  27. 		if(!visited[z]){
  28. 			visited.set(z);
  29. 			tmp=cur_d;
  30. 			cur_d+=abs(beepers[z].first-from.first)+abs(beepers[z].second-from.second);
  31. 			if(cur_d<min_d)
  32. 			rcr(beepers[z]);
  33. 			cur_d=tmp;
  34. 			visited.reset(z);
  35. 		}
  36. }
  37. int main() {
  38. 	int t, i, j;
  39. 	cin>>t;
  40. 	while(t--){
  41. 		cin>>m>>n>>x>>y>>sz;
  42. 		pair<int, int> o=pair<int, int>(x, y);
  43. 		beepers.clear();
  44. 		min_d=99999999;
  45. 		visited.set();
  46. 		for(int k=0;k<sz;k++){
  47. 			visited.reset(k);
  48. 			cin>>i>>j;
  49. 			beepers.push_back(pair<int, int>(i,j));
  50. 		}
  51. 		cur_d=0;
  52. 		rcr(o);
  53. 		printf("The shortest path has length %d\n", min_d);
  54. 		//if(t) putchar('\n');
  55. 	}
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
1
10 10
1 1
4
2 3
5 5
9 4
6 5
stdout
copy 
The shortest path has length 24
https://ideone.com/S2bW1I
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!