记录编号	159981	评测结果	AAAAAAAAAAAAAAA
题目名称	马拉松2	最终得分	100
用户昵称	wolf.	是否通过	通过
代码语言	C++	运行时间	0.582 s
提交时间	2015-04-23 15:13:25	内存使用	0.29 MiB

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
ifstream fin("marathonb.in");
ofstream fout("marathonb.out");
class node{
public:
	int x,y;
	node(){
	}
	node(int a,int b){
		x=a;
		y=b;
	}
};
class llink{
public:
	int n,k;
	llink(){
	}
	llink(int a,int b){
		n=a;
		k=b;
	}
};
const int IMAX=999999999;
///////////////////////////////////
vector<node> PP;
int calc(int x1,int y1,int x2,int y2){
	return abs(x1-x2)+abs(y1-y2);
}
int ana(int a,int b){
	return calc(PP[a].x,PP[a].y,PP[b].x,PP[b].y);
}
///////////////////////////////////
vector<vector<int> > TT;
vector<vector<bool> > flag;
long long core(int n,int k){
	TT[0][k]=0;
	queue<llink> Q;
	Q.push(llink(0,k));
	while(!Q.empty()){
		llink pp=Q.front();
		Q.pop();
		flag[pp.n][pp.k]=0;
		//cout<<pp.n<<"  "<<pp.k<<endl;
		for(int i=1;pp.n+i<PP.size()&&i<=pp.k+1;++i){
			int r=ana(pp.n,pp.n+i);
			int kk=pp.k-(i-1);
			//cout<<pp.n+i<<"  "<<kk<<"  "<<r<<endl;
			if(TT[pp.n+i][kk]>TT[pp.n][pp.k]+r){
				TT[pp.n+i][kk]=TT[pp.n][pp.k]+r;
				if(flag[pp.n+i][kk]==0){
					flag[pp.n+i][kk]=1;
					Q.push(llink(pp.n+i,kk));
				}
			}
		}
	}
	int ans=IMAX;
	for(int i=0;i!=TT[n-1].size();++i){
		ans=min(TT[n-1][i],ans);
	}
	return ans;
}
int main(){
	int n,k;
	fin>>n>>k;
	TT.resize(n);
	flag.resize(n);
	for(int i=0;i!=n;++i){
		TT[i].resize(k+1,IMAX);
		flag[i].resize(k+1,0);
		int a,b;
		fin>>a>>b;
		PP.push_back(node(a,b));
	}
	fout<<core(n,k);
	return 0;
}
//designde by wolf