记录编号	47586	评测结果	AAAAAEEEEE
题目名称	[Poetize 9] 升降梯上	最终得分	50
用户昵称	feng	是否通过	未通过
代码语言	C++	运行时间	0.408 s
提交时间	2012-11-02 10:43:32	内存使用	7.11 MiB

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
struct node{
	int s,nex;
}a[40100];
struct edge{
	int y,v,nex;
}e[800000];
int n,m,p;
int dis[40010];
bool f[40010];
int queue[10000];
int aa[40010];
void add(int x,int y,int v){
	p++;
	a[x].s++;
	e[p].y=y;
	e[p].v=v;
	e[p].nex=a[x].nex;
	a[x].nex=p;
}
void init()
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
					int x=i*m+j;
					int y=i*m+j-1;
					if (j>1)
					add(x,y,1);
					y=i*m+j+1;
					if (j<m)
					add(x,y,1);
				}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (aa[j]!=0){
				int tmp=i+aa[j];
				if (tmp<=n && tmp>0){
					int x=i*m+j;
					int y=(i+aa[j])*m+j;
					int v=abs(aa[j])*2;
					add(x,y,v);
				}
			}
}
void SPFA(){
	int s;
	int t;
	int tmp;
	for (int i=1;i<=m;i++)
		if (aa[i]==0)
			s=m+i;
	memset(f,true,sizeof(f));
	memset(dis,1,sizeof(dis));
	memset(queue,0,sizeof(queue));
	f[s]=false;
	dis[s]=0;
	int head=0;
	int tail=1;
	queue[tail]=s;
	while (head<=tail){
		head++;
		tmp=queue[head];
		f[tmp]=true;
		t=a[tmp].nex;
		for (int i=1;i<=a[tmp].s;i++){
			if (dis[tmp]+e[t].v<dis[e[t].y]){
				dis[e[t].y]=dis[tmp]+e[t].v;
				if (f[e[t].y]){
					f[e[t].y]=false;
					queue[++tail]=e[t].y;
				}
			}
			t=e[t].nex;
		}
	}
	
}
int main()
{
	freopen("updown.in","r",stdin);
	freopen("updown.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
		scanf("%d",&aa[i]);
	p=0;
	init();
	SPFA();
	int ans=dis[1];
	int o=12;
	for (int i=n*m+1;i<=n*m+m;i++)
		if (dis[i]<ans) ans=dis[i];
	if (ans==dis[0]) ans=-1;
	printf("%d\n",ans);
	return 0;
}