记录编号	7865	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.605 s
提交时间	2008-11-11 22:13:30	内存使用	48.37 MiB

#include <iostream>
#include <fstream>

#define MAXN 53
#define MAXP 2510
#define INF 999999999

using namespace std;

ifstream fin ("eldrethalas.in");
ofstream fout("eldrethalas.out");

const int Dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,p,hp,ans,cost[MAXP],map[MAXN][MAXN],data[MAXP][MAXP],dis[MAXP],adj[MAXP][MAXP],que[MAXP];

void dij(int src)
{
	const int P=MAXP-5;
	int i,x,y,head,tail,isin[MAXP]={0};
	memset(dis,127,sizeof(dis));
	dis[src]=0;
	que[0]=src;
	head=-1;
	tail=0;
	isin[src]=1;
	while (head<tail)
	{
		x=que[(++head)%P];
		//relax
		for (i=1;i<=adj[x][0];i++)
		{
			y=adj[x][i];
			if (dis[x]+data[x][y]<dis[y])
			{
				dis[y]=dis[x]+data[x][y];
				if (isin[y]==0)
				{
					isin[y]=1;
					que[(++tail)%P]=y;
				}
			}
		}
		isin[x]=0;
	}
}

void run()
{
	int j1,j2,c1,c2,done[MAXP]={0};
	ans=INF;
	for (j1=1;j1<=n;j1++)
	{
		c1=map[1][j1];
		dij(c1);
		for (j2=1;j2<=n;j2++)
		{
			c2=map[n][j2];
			if (dis[c2]+cost[c1]<ans)
				ans=dis[c2]+cost[c1];
		}
	}
	ans=hp-ans;
	if (ans>0)
		fout<<ans;
	else
		fout<<"NO";
}

void ini()
{
	int i,j,d,a,b,c1,c2;
	fin>>n>>p>>hp;
	for (i=0;i<=p;i++)
		for (j=0;j<=p;j++)
			if (i!=j)
				data[i][j]=INF;
	for (i=1;i<=p;i++)
	{
		fin>>cost[i];
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			fin>>map[i][j];
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			c1=map[i][j];
			for (d=0;d<4;d++)
			{
				a=i+Dir[d][0];
				b=j+Dir[d][1];
				if (a>=1 && a<=n && b>=1 && b<=n)
				{
					c2=map[a][b];
					if (c1!=c2)
					{
						if (data[c1][c2]==INF)
							adj[c1][++adj[c1][0]]=c2;
						data[c1][c2]=cost[c2];
					}
				}
			}
		}
			
	
}

int main()
{
	ini();
	run();
	return 0;
}