记录编号	159948	评测结果	AAAAAAAAAAAAAAA
题目名称	马拉松2	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.460 s
提交时间	2015-04-23 12:47:44	内存使用	2.48 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<algorithm>
using namespace std;
int N,K,maxn=0xffffff;
long long p[501][501],ans=maxn;
bool q[501][501];
class poi
{
public:
	int x;
	int y;	
}cow[501];
class miku
{
public:
	int i,k;
	long long& val(void)
	{
		return p[i][k];
	}
	bool& iq(void)
	{
		return q[i][k];
	}
};
int dis(const poi &a,const poi &b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
deque<miku> Q;
void check(miku a,long long b)
{
	if(b<a.val())
	{
		a.val()=b;
		if(!a.iq())
		{
			a.iq()=true;
			Q.push_back(a);
		}
	}
}
int bfs()
{
	miku x;
	x.i=1;x.k=K;
	x.val()=0;
	x.iq()=false;
	Q.push_back(x);
	miku s,t;
	while(!Q.empty())
	{
		s=Q.front();Q.pop_front();s.iq()=0;long long w=s.val();
		for(int i=0;i<=s.k&&s.i+i+1<=N;i++)
		{
		t=s;t.i+=(i+1);t.k-=i;
		check(t,w+dis(cow[s.i],cow[t.i]));
		}
	}
	return 0;
}
int main()
{
	freopen("marathonb.in","r",stdin);
	freopen("marathonb.out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++) scanf("%d%d",&cow[i].x,&cow[i].y);
	for(int i=1;i<=N;i++)
		for(int j=0;j<=K;j++)
			p[i][j]=maxn;
	bfs();
	for(int i=0;i<=K;i++)
	{
		ans=min(p[N][i],ans);
	}
	cout<<ans;
	return 0;
}