6 7 10
3
1
2
2
1
1
3
1 1 1 2 2 3
1 2 3 3 3 3
1 1 2 2 4 4
5 5 5 5 5 6
5 7 7 5 6 6
7 7 6 6 6 6
7
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int N=110; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; struct node{ int to,next,w; }a[N*N*4]; int n,p,h,tot,ans; int ls[N*N],f[N*N],power[N][N],w[N*N]; bool v[N*N]; queue<int> q; void add(int x,int y,int w) { a[++tot].next=ls[x]; a[tot].to=y; a[tot].w=w; ls[x]=tot; } void spfa() { memset(f,0x3f,sizeof(f)); q.push(0);v[0]=1;f[0]=0; while(!q.empty()){ int x=q.front();q.pop();v[x]=0; for(int i=ls[x];i;i=a[i].next){ int y=a[i].to; if(f[x]+a[i].w<f[y]){ f[y]=f[x]+a[i].w; if(!v[y]){ v[y]=1; q.push(y); } } } } } int main() { scanf("%d%d%d",&n,&p,&h); for(int i=1;i<=p;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&power[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ for(int k=0;k<4;k++) { int x=i+dx[k],y=j+dy[k]; if(!power[x][y]||power[i][j]==power[x][y]) continue; add(power[i][j],power[x][y],w[power[x][y]]); } } for(int i=1;i<=n;i++) add(0,power[1][i],w[power[1][i]]); spfa(); for(int i=1;i<=n;i++) ans=max(ans,h-f[power[n][i]]); if(ans>0) printf("%d",ans); else printf("NO"); }
原文：https://www.cnblogs.com/zjzjzj/p/10778886.html