4852474_ac_0ms_280k.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;
int x,y;
struct point
{
	int x,y;
}q[15],inin[15];
int quan[15];
int n;
int getit()
{
	int i,all=0;
	int tx,ty;
	for(i=0;i<n;i++)
	{
		tx=q[i+1].x-q[i].x;if(tx<0)tx*=-1;
		ty=q[i+1].y-q[i].y;if(ty<0)ty*=-1;
		all+=tx+ty;
	}
	tx=q[n].x-q[0].x;if(tx<0)tx*=-1;
	ty=q[n].y-q[0].y;if(ty<0)ty*=-1;
	all+=tx+ty;
	return all;
}
int main()
{
	int testnumber,i,best;
	cin>>testnumber;
	for(int count=0;count<testnumber;count++)
	{
		cin>>x>>y;
		cin>>q[0].x>>q[0].y;
		cin>>n;
		best=999999999;
		for(i=1;i<=n;i++)
		{
			cin>>inin[i].x>>inin[i].y;
		}
		for(i=0;i<n;i++)
		{
			quan[i]=i+1;
		}
		do
		{
			for(i=1;i<=n;i++)q[i]=inin[quan[i-1]];
			int t=getit();
			if(t<best)best=t;
		}while(next_permutation(quan,quan+n));
		cout<<"The shortest path has length "<<best<<endl;
	}
	return 0;
}