poj 2907 Collecting Beepers 郵遞員問題暴力解法

題意：

給起點和n個點，求從起點出發經過這n個點每個點至少一次再回到起點的最短路。

分析：

類似郵遞員問題，直接用STL枚舉訪問順序暴力解決。

代碼：

//poj 2907
//sep9
#include 
#include 
using namespace std;
int x[16],y[16];
int d[16][16];
int a[16];
int n;
int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		scanf("%*d%*d%d%d",&x[0],&y[0]);			
		int i,j,n;
		scanf("%d",&n);
		for(i=1;i<=n;++i)
			scanf("%d%d",&x[i],&y[i]);
		for(i=0;i<=n;++i)
			for(j=i;j<=n;++j)
				d[i][j]=d[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
		int ans=INT_MAX;
		for(i=0;i<=n;++i)
			a[i]=i;
		do{
			int sum=0;
			for(int i=1;i<=n;++i)
				sum+=d[a[i-1]][a[i]];
			sum+=d[a[n]][a[0]];
			ans=min(ans,sum);
		}while(next_permutation(a+1,a+1+n));
		printf("The shortest path has length %d\n",ans);
	}	
	return 0;	
}