正題

jzoj題目鏈接:https://jzoj.net/senior/#main/show/5309

---

題目大意

有n個(gè)點(diǎn)，m條邊,k種鑰匙。有些點(diǎn)分布了鑰匙，有些邊需要一些鑰匙才可以通過(guò)，求1到n的最短路。

---

解題思路

將圖分成2k2k層，每一層用二進(jìn)制表示不同的鑰匙情況。然后根據(jù)不同情況連邊就好了。
(雙端隊(duì)列bfs會(huì)莫名其妙WA一個(gè)點(diǎn))

---

code

#include<cstdio> #include<queue> #include<cstring> #define p(x,y) x*n+y #define N 5110 #define M 6110 #define MS 1024 using namespace std; struct node{int to,next;bool w; }a[MS*(N+M)]; int n,m,k,x,y,w,MAX_State,d[N*MS],tot,ls[N*MS]; bool v[N*MS]; queue<int> q; void addl(int x,int y,int w)//加邊 {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void bfs()//SPFA {memset(d,127/3,sizeof(d));q.push(p(0,1));d[p(0,1)]=0;v[p(0,1)]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(d[x]+a[i].w<d[y]){d[y]=d[x]+a[i].w;if(!v[y]){v[y]=true;q.push(y);}}}v[x]=false;} } int main() {scanf("%d%d%d",&n,&m,&k);MAX_State=1<<k;for(int i=1;i<=n;i++)for(int j=1;j<=k;j++){scanf("%d",&x);if(x){for(int state=0;state<MAX_State;state++)addl(p(state,i),p((state|(1<<(j-1))),i),0);//不同情況的獲取鑰匙}}for(int i=1;i<=m;i++){int state=0;scanf("%d%d",&x,&y);for(int i=1;i<=k;i++){scanf("%d",&w);state+=w<<(i-1);}for(int j=0;j<MAX_State;j++)if((j&state)==state)addl(p(j,x),p(j,y),1);//滿足鑰匙的情況連邊}bfs();int ans;ans=2147483647;for(int j=0;j<MAX_State;j++)ans=min(ans,d[p(j,n)]);//因?yàn)闆](méi)有要求鑰匙狀態(tài)所以取最小的if(ans>10000) printf("No Solution");else printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的nssl1150,jzoj5309-密室【分层建图,SPFA】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。