uva10496 - TSP

uva10496.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }


const int maxn=(int)4e5+5;
const int inf = 1e9;


int dist(int x, int y, int a, int b) {
  return abs(x-a) + abs(y-b);
}

void solve() {
  int X,Y; cin>>X>>Y;
  int x,y; cin>>x>>y;
  int n; cin>>n;
  vector<int> bx(n), by(n);
  for (int i=0; i<n; i++) {
    cin>>bx[i]>>by[i];
  }
  vector<vector<int>> dp(1<<n, vector<int>(n+1, inf));
  dp[0][0] = 0;

  for (int mask=1; mask < (1<<n); mask++) {
    for (int j=1; j<=n; j++) {
      if (((mask>>(j-1))&1) == 0) continue;

      int prevmask = mask ^ (1 << (j-1));
      if (prevmask == 0) {
	dp[mask][j] = dist(x,y,bx[j-1],by[j-1]);
      } else {
	for (int k=1; k<=n; k++) {
	  if (((prevmask >> (k-1))&1) == 0) continue;
	  //int prevprevmask = prevmask ^ (1 << (k-1));
	  int dst = dist(bx[k-1],by[k-1],bx[j-1],by[j-1]);
	  dp[mask][j] = min(dp[mask][j], dp[prevmask][k] + dst);
	}
      }      
    }
  }

  int vizall = (1<<n) - 1;
  int ans = inf;
  for (int end=1; end<=n; end++) {
    int back = dist(x,y,bx[end-1],by[end-1]);
    ans = min(ans, back+dp[vizall][end]);
  }

  cout<<"The shortest path has length "<<ans<<endl;
}


int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  //cout << fixed << setprecision(6);
  int t; cin>>t;
  while(t--) solve();

  return 0;
}