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;
}
Runtime: 0.022
Ideone: http://ideone.com/S2bW1I

Comments

Popular Posts