【csp模拟赛九】--dfs

思路：

　　这道题可以宽搜，深搜，最短路

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<queue>

using namespace std;

queue<pair<int,int> > q;

int n,m,c[25],s;

long long f[25][1010],ans;

bool v[25][1010];

int Abs(int x)

{

	return x >= 0 ? x : -x;

}

void bfs()

{

	q.push(make_pair(s,1));

	v[s][1] = 1;	f[s][1] = 0;

	while(!q.empty())

	{

		int x = q.front().first;

		int y = q.front().second;

		q.pop();	v[x][y] = 0;

		for(int i = 1;i <= m;i ++)

		{

			int em = y + c[i];

			if(em <= n && em >= 1)

			{

				if(f[i][em] > f[x][y] + Abs(i - x) + Abs(2 * c[i]))

				{

					f[i][em] = f[x][y] + Abs(i - x) + Abs(2 * c[i]);

					if(!v[i][em])	q.push(make_pair(i,em)),v[i][em] = 1;

				}

			}

		}

	}

}

int main()

{

	freopen("elevator.in","r",stdin);

	freopen("elevator.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;i ++)

	{

		scanf("%d",&c[i]);

		if(c[i] == 0)	s = i;

	}

	memset(f,0x3f,sizeof(f));

	ans = f[0][0];

	bfs();

	for(int i = 1;i <= m;i ++)	ans = min(ans,f[i][n]);

	if(ans != f[0][0])	printf("%d\n",ans);

	else	printf("-1\n");

	fclose(stdin);

	fclose(stdout);

	return 0;

}

/*

6 3

-1 0 2

*/