[UVa] 1347 - Tour

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1347 - Tour
Source            : UVa Online Judge
Category          : Dynamic Programing
Algorithm         : Bitonic TSP
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1e3 + 5;
 
struct point
{
       double x, y;
       point(double xx = 0.0, double yy = 0.0)
       {
              this->x = xx;
              this->y = yy;
       }
       inline void read()
       {
              double xx, yy;
              cin >> xx >> yy;
              x = xx;
              y = yy;
       }
} Points[maxn];
 
 
inline double dist(const point p, const point q)
{
       double xx = (p.x - q.x) * (p.x - q.x) * 1.0;
       double yy = (p.y - q.y) * (p.y - q.y) * 1.0;
       return sqrt(xx + yy);
}
 
int tpoint;
double distanc[maxn][maxn];
double dp[maxn][maxn];
bool vis[maxn][maxn];
 
inline double bitonicTSP(int p1, int p2)
{
       int v = 1 + max(p1, p2);
       if (v == tpoint - 1) return distanc[p1][v] + distanc[v][p2];
       double &ret = dp[p1][p2];
       bool &viss = vis[p1][p2];
       if (viss) return ret;
       viss = 1;
       ret = min(distanc[p1][v] + bitonicTSP(v, p2),
                 distanc[v][p2] + bitonicTSP(p1, v));
       return ret;
}
 
int main()
{
       //freopen("in.txt", "r", stdin);
 
       while (cin >> tpoint)
       {
              for (int i = 0; i < tpoint; i++) Points[i].read();
              for (int i = 0; i < tpoint; i++)
              {
                     for (int j = 0; j < tpoint; j++)
                     {
                            distanc[i][j] = dist(Points[i], Points[j]);
                     }
              }
              memset(vis, 0, sizeof vis);
              double ans = bitonicTSP(0, 0);
              cout << fixed << setprecision(2) << ans << endl;
       }
}