# Poj Solution 2907

```http://poj.org/problem?id=2907

#include <functional>
//#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

int s[11][1<<10][10];
typedef pair<int,int> point;
point p;
point b[10];

int dis( point &a, point &b ) {
return abs(a.first-b.first) + abs(a.second-b.second);
}

int main( ) {
int i, j, n, m, se, h, k, l;
scanf( "%d", &se );
while( se-- ) {
scanf( "%d%d", &n, &m );
scanf( "%d%d", &p.first, &p.second );
scanf( "%d", &h );
for( i=0; i<h; i++ )
scanf( "%d%d", &b[i].first, &b[i].second );

memset( s, -1, sizeof s );

for( i=0; i<h; i++ ) {
s[0][1<<i][i] = dis( p, b[i] );
}

for( l=0; l<h-1; l++ ) {
for( i=0; i<h; i++ )
for( j=0; j<h; j++ )
if( i != j ) {
for( k=0; k<(1<<h); k++ )
if( s[l][k][i] >= 0 && ((1<<j)&k) == 0 &&
( s[l+1][(1<<j)|k][j] == -1 || s[l+1][(1<<j)|k][j] > s[l][k][i]+dis( b[i], b[j] ) )
) {
s[l+1][(1<<j)|k][j] = s[l][k][i] + dis( b[i], b[j] );
//                        printf( "%d %d %dn", l+1, j, s[l+1][(1<<j)|k][j] );
}
}
}

int ans = 9999999;
for( i=0; i<h; i++ )
for( k=0; k<(1<<h); k++ )
if( s[h-1][k][i] >= 0 && ans > s[h-1][k][i] + dis( b[i], p ) )
ans = s[h-1][k][i] + dis( b[i], p );
printf( "The shortest path has length %dn", ans );
}
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.