UVa 10496 - Collecting Beepers
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <bitset> #include <stdio.h> #include <math.h> using namespace std; typedef std::vector<int> vi; typedef std::vector<pair<int, int> > vii; #define FOR(l) for(vi::iterator it=l.begin();it!=l.end();it++) #define FOR_L(l, s, e) for(vi::iterator it=l.begin()+s;it!=l.end()-e;it++) //----------Main source code -----------------// int m, n, x, y, min_d, cur_d, sz; vii beepers; bitset<11> visited; void rcr(pair<int, int> &from){ int tmp; if(visited.all()){ tmp=cur_d; cur_d+=abs(x-from.first)+abs(y-from.second); if(cur_d<min_d) min_d=cur_d; cur_d=tmp; return; } for(int z=0;z<sz;z++) if(!visited[z]){ visited.set(z); tmp=cur_d; cur_d+=abs(beepers[z].first-from.first)+abs(beepers[z].second-from.second); if(cur_d<min_d) rcr(beepers[z]); cur_d=tmp; visited.reset(z); } } int main() { int t, i, j; cin>>t; while(t--){ cin>>m>>n>>x>>y>>sz; pair<int, int> o=pair<int, int>(x, y); beepers.clear(); min_d=99999999; visited.set(); for(int k=0;k<sz;k++){ visited.reset(k); cin>>i>>j; beepers.push_back(pair<int, int>(i,j)); } cur_d=0; rcr(o); printf("The shortest path has length %d\n", min_d); //if(t) putchar('\n'); } return 0; }
Ideone: http://ideone.com/S2bW1I
Comments
Post a Comment