你看见宝藏就在你的前方不远处。但是你不能贸然前进，因为路上有着强大的魔法结界。
这些结界根据能量的不同分为PPP种，踏入每种结界，你都会受到一定的伤害。为了拿到宝藏，这些伤害算不了什么。但是你要尽可能地减少伤害。
请你设计一条路线，使你穿越结界获取宝藏受到的伤害最少。结界是一个正方形，内部有PPP种不同的能量，每种字母表示一种能量。你从最上端开始走，每次可以走到与你所在的位置上下左右相邻的临位，或者在同种能量结界中任意传送。重复进入同一种能量结界不会再次受到伤害。
题目解析
方法一：
直接宽搜也可以
预处理所有同种能量结界的坐标
从最上面的一层开始，往下更新出到(i,j)(i,j)(i,j)的位置的最小伤害值
在最下面那一层找最小值KKK即可
若K<HK<HK<H，则输出H−KH-KH−K。否则输出NONONO
方法二：由于在同种结界能可以任意传送，而且不会再次受到伤害，我们不妨把同种结界收缩成一个单元。由于只能踏入相邻的单元格，只需考虑收缩后的单元之间的关系。用图来描述。在此基础上，我们再加入一个超级源和超级汇，表示起始点和宝藏的位置。
我们把每个顶点赋予权值，为踏入这种结界的伤害值。从起点拿到宝藏收到的最小伤害，就是求从超级源000到超级汇P+1P+1P+1，经过的最小点权
把点权无向图转化为边权有向图。除了连接超级源和超级汇的边，每条边变成两条有向边，边权为有向边指向的顶点的原点权。
求最短路即可
代码
方法一的代码
#include<bits/stdc++.h>usingnamespacestd;structA{intx,y;};intn,p,h,ans=1e9;inta[3005],mapa[55][55],f[55][55],fx[4][2]={{0,1},{1,0},{-1,0},{0,-1}};boolvis[55][55];vector<A>b[3005];queue<A>q;intmain(){memset(f,0x3f,sizeof(f));intM=f[0][0];scanf("%d%d%d",&n,&p,&h);for(inti=1;i<=p;i++)scanf("%d",&a[i]);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf("%d",&mapa[i][j]),b[mapa[i][j]].push_back((A){i,j});for(inti=1;i<=n;i++)if(!vis[1][i]){for(intj=0;j<b[mapa[1][i]].size();j++){f[b[mapa[1][i]][j].x][b[mapa[1][i]][j].y]=a[mapa[1][i]];vis[b[mapa[1][i]][j].x][b[mapa[1][i]][j].y]=1;q.push((A){b[mapa[1][i]][j].x,b[mapa[1][i]][j].y});}}while(!q.empty()){Aff;ff=q.front();q.pop();vis[ff.x][ff.y]=0;intx,y;for(inti=0;i<4;i++){x=ff.x+fx[i][0];y=ff.y+fx[i][1];if(x<1||x>n||y<1||y>n)continue;if(f[x][y]>a[mapa[x][y]]+f[ff.x][ff.y]){for(intj=0;j<b[mapa[x][y]].size();j++){if(f[b[mapa[x][y]][j].x][b[mapa[x][y]][j].y]>a[mapa[x][y]]+f[ff.x][ff.y]){f[b[mapa[x][y]][j].x][b[mapa[x][y]][j].y]=a[mapa[x][y]]+f[ff.x][ff.y];if(vis[b[mapa[x][y]][j].x][b[mapa[x][y]][j].y]==0){vis[b[mapa[x][y]][j].x][b[mapa[x][y]][j].y]=1;q.push((A){b[mapa[x][y]][j].x,b[mapa[x][y]][j].y});}}}}}}for(inti=1;i<=n;i++)ans=min(ans,f[n][i]);if(h>ans)printf("%d",h-ans);elseprintf("NO");return0;}
