记录编号	345222	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	1.196 s
提交时间	2016-11-10 21:22:29	内存使用	72.46 MiB

#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define maxn 55
int t[maxn][maxn],len,head[maxn*maxn],n,val[maxn*maxn],m,h,dis[maxn*maxn];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},ans=0x7f7f7f7f;
struct edge{
	int to,next,dis;
}a[2510*2510];
struct node{
	int x,dis;
	node(int a,int b){
		x=a;dis=b;
	}
	bool operator<(const node&a)const{
		return a,dis<dis;
	}
};
void insert(int x,int y,int z){
	len++;a[len].to=y;a[len].next=head[x];a[len].dis=z;head[x]=len;
	//cout<<len<<" "<<x<<" "<<y<<" "<<z<<endl;
}
void dijs(int x){
	priority_queue<node>q;
	memset(dis,0x7f,sizeof dis);
	dis[x]=val[t[1][x]];q.push(node(x,val[t[1][x]]));
	while(!q.empty()){
		node k=q.top();q.pop();
		if(k.dis!=dis[k.x])continue;
		if(k.dis>h)continue;
		for(int i=head[k.x];i;i=a[i].next){
			int to=a[i].to;
			if(dis[to]>dis[k.x]+a[i].dis){
				dis[to]=dis[k.x]+a[i].dis;
				q.push(node(to,dis[to]));
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[(n-1)*n+i]<h)ans=min(ans,dis[(n-1)*n+i]);
	}
}		
int main(){
	freopen("eldrethalas.in","r",stdin);
	freopen("eldrethalas.out","w",stdout);
	scanf("%d%d%d",&n,&m,&h);
	for(int i=1;i<=m;i++)scanf("%d",&val[i]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)scanf("%d",&t[i][j]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		for(int k=0;k<4;k++){
			int xx=i+dx[k],yy=j+dy[k];
			if(xx<1||yy<1||xx>n||yy>n)continue;
			else insert((i-1)*n+j,(xx-1)*n+yy,val[t[xx][yy]]);
		}
		for(int p=1;p<=n;p++)
		for(int q=1;q<=n;q++){
			if(p==i&&q==j)continue;
			if(t[i][j]!=t[p][q])continue;
			insert((i-1)*n+j,(p-1)*n+q,0);
		}
	}
	for(int i=1;i<=n;i++)dijs(i);
	if(ans<0x7f7f7f7f)printf("%d",h-ans);
	else printf("NO");
	//while(1);
}