记录编号	359287	评测结果	AAAAAWWEWA
题目名称	[USACO Dec16]萌化大革命	最终得分	60
用户昵称	liu_runda	是否通过	未通过
代码语言	C++	运行时间	0.139 s
提交时间	2016-12-21 21:45:12	内存使用	5.90 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=905;
int n1,n2;
int x1[maxn],x2[maxn],y1[maxn],y2[maxn];
int f[maxn][maxn][2];
int dis(int x1,int y1,int x2,int y2){
  return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
int main(){
  freopen("checklist.in","r",stdin);
  freopen("checklist.out","w",stdout);
  scanf("%d%d",&n1,&n2);  
  for(int i=1;i<=n1;++i)scanf("%d%d",x1+i,y1+i);
  for(int i=1;i<=n2;++i)scanf("%d%d",x2+i,y2+i);
  memset(f,0x3f,sizeof(f));
  f[1][0][0]=0;
  for(int i=1;i<=n1;++i){
    for(int j=0;j<=n2;++j){
      if(i==1&&j==0)continue;
      f[i][j][0]=min(f[i-1][j][0]+dis(x1[i],y1[i],x1[i-1],y1[i-1]),f[i-1][j][1]+dis(x1[i],y1[i],x2[j],y2[j]));
      if(j!=0)f[i][j][1]=min(f[i][j-1][0]+dis(x1[i],y1[i],x2[j],y2[j]),f[i][j-1][1]+dis(x2[j-1],y2[j-1],x2[j],y2[j]));
    }
  }
  printf("%d\n",f[n1][n2][0]);
  fclose(stdin);fclose(stdout);
  return 0;
}