社区讨论

为什么BFS就不对呢

P3489[POI 2009] WIE-Hexer参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi86km28
此快照首次捕获于
2025/11/21 09:27
4 个月前
此快照最后确认于
2025/11/21 09:27
4 个月前
查看原帖
RT
CPP
#include<bits/stdc++.h>
#define REP(i,a,b) for(register int i(a);i<=b;i++)
using namespace std;
const int N=209;
const int P=20;
const int M=3100;
int n,m,p,k,t,x,y,ks,pos,INF;
int G[N][N];
int C[N][N];
int att[N];
int ans,bs;
struct node{int po,sw,res;
};
queue<node>q;
template<class T>inline void read(T &x) {
	T res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {res=res*10+ch-'0';ch=getchar();}
	x=res*f;
}
inline int min(int a,int b){return a<b?a:b;}
inline void BFS(int st){
	q.push((node){st,0|att[st],0});
	while(q.size()){
		int x=q.front().po,s=q.front().sw,rr=q.front().res;q.pop();
		if(x==n){ans=min(ans,rr);if(clock()>850)return;}
		REP(i,1,n)
		if(G[x][i]!=INF&&((C[x][i]&s)==C[x][i])&&(rr+G[x][i]<=ans))
		q.push((node){i,s|att[i],rr+G[x][i]});
	}
}
int main() {
//	freopen("fsz.in","r",stdin);
//	freopen("fsz.out","w",stdout);
	memset(G,0x3f,sizeof(G));INF=G[1][1];ans=INF;
	read(n);read(m);read(p);read(k);
	REP(i,1,k) {
		read(pos);read(ks);
		REP(j,1,ks){read(t);att[pos]|=1<<(t-1);}
	}
	REP(i,1,m) {
		read(x);read(y);read(t);
		G[x][y]=G[y][x]=min(G[x][y],t);
		read(ks);
		REP(j,1,ks) {read(t);C[x][y]|=1<<(t-1);C[y][x]|=1<<(t-1);}
	}
	BFS(1);
	if(ans==INF)cout<<-1;
	else cout<<ans;
//	fclose(stdin);fclose(stdout);
}

回复

3 条回复,欢迎继续交流。

正在加载回复...