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;
}