uva 216 - Getting in Line

  1 /*
  2  Problem link
  3  Type: DP - TSP
  4  Algorithm: Brute force, back-tracking
  5  */
  6  #include <iostream>
  7  #include <cstdio>
  8  #include <cstring>
  9  #include <cmath>
 10  #include <cstdlib>
 11  #include <map>
 12  #include <vector>
 13  using namespace std;
 14  const int maxn = 10;
 15  
 16  class Point
 17  {
 18  public:
 19      int x,y;
 20      Point() {}
 21      Point(int xx,int yy): x(xx), y(yy) {}
 22  };
 23  
 24  map<int,Point> pList;
 25  bool visited[maxn];
 26  vector<int> ans,ansOpt;
 27  int n;
 28  double result;
 29  
 30  bool ReadFile();
 31  void Attempt(int i, double sum);
 32  double dist(Point a, Point b);
 33  
 34  int main()
 35  {
 36      int test = 0;
 37      while (ReadFile())
 38      {
 39          test++;
 40          ans.clear();
 41          ansOpt.clear();
 42          result = 20000000;
 43          Attempt(1,0);
 44          cout << "**********************************************************" << endl;
 45          printf("Network #%d\n",test);
 46          for (unsigned int i=1; i<ansOpt.size(); i++)
 47              printf("Cable requirement to connect (%d,%d) to (%d,%d) is %0.2f feet.\n",pList[ansOpt[i-1]].x,
 48                     pList[ansOpt[i-1]].y, pList[ansOpt[i]].x,pList[ansOpt[i]].y,dist(pList[ansOpt[i]],pList[ansOpt[i-1]])+16);
 49          printf("Number of feet of cable required is %0.2f.\n",result);
 50      }
 51  }
 52  
 53  bool ReadFile()
 54  {
 55      cin >> n;
 56      if (n==0) return(false);
 57      for (int i=1; i<=n; i++)
 58      {
 59          int x,y;
 60          cin >> x >> y;
 61          pList[i] = Point(x,y);
 62      }
 63      return true;
 64  }
 65  
 66  void Attempt(int i, double sum)
 67  {
 68      if (i==n+1)
 69      {
 70          if (sum<result)
 71          {
 72              result = sum;
 73              ansOpt = ans;
 74          }
 75          return;
 76      }
 77      for (int j=1; j<=n; j++)
 78          if (!visited[j])
 79          {
 80              visited[j] = true;
 81              ans.push_back(j);
 82              int pre,cur;
 83              if (ans.size()>1)
 84              {
 85                  pre = ans[ans.size()-2];
 86                  cur = ans[ans.size()-1];
 87              }
 88              else pre = cur = ans[ans.size()-1];
 89              if (i>1) Attempt(i+1,sum+dist(pList[pre],pList[cur])+16);
 90              else Attempt(i+1,sum+dist(pList[pre],pList[cur]));
 91              visited[j] = false;
 92              ans.erase(ans.end()-1);
 93          }
 94  }
 95  
 96  double dist(Point a, Point b)
 97  {
 98      return(sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
 99  }