社区讨论
为什么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 条回复,欢迎继续交流。
正在加载回复...