2907.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2907  User Id:fzk 
Memory:488K  Time:0MS
Language:C++  Result:Accepted

Source 

//#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 %d\n", 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 %d\n", ans );
	}
	return 0;
}