正題

---

題目大意

從第一列出發，到最后一列，然后可以傳送到相同的魔法格里，經過不同的魔法格會損傷不同的生命(如果之前經過過就不會)。求最大剩余生命。

---

解題思路

因為相同的魔法格可以傳送，所以你肯定不會回到相同的魔法格兩次，所以我們將一種魔法格定義為一個點，然后相鄰的不同的魔法格之間就連邊。

---

$code$

#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 addl(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;addl(power[i][j],power[x][y],w[power[x][y]]);}}for(int i=1;i<=n;i++)addl(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"); }

總結

以上是生活随笔為你收集整理的nssl1319-埃雷萨拉斯寻宝【SPFA,建图】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。