2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛———B. 精神胜利（位集bfs） · znzryb
## 思路讲解
dij 不能用，因为边太多了。
因为边权只有0 和 1，可以使用位集 bfs。
## AC代码
AC
[https://qoj.ac/submission/1411426](https://qoj.ac/submission/1411426)
判断一下是否可以两次抵达，196ms
::: 源代码
```cpp
// by Gospel_rock
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)5e3+10,INF=(ll)1e17+3; // 1e17+3??? 1e18+9???
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
struct Solve{
vector<bitset<MAXN>> A; // ???OUT?
vector<bitset<MAXN>> IN; // ???IN????????????
vector<vll> Dis; // Dis[u][v] = (???? - 1)???? -1
bitset<MAXN> ised; // ????? u ?? BFS ??
Solve(){
cin>>N>>Q;
A.resize(N+5);
IN.resize(N+5);
Dis.resize(N+5, vll(N+5, -1));
// ??????? i ?? j=i+1..N
FOR(i,1,N){
FOR(j,1,N-i){
char a; cin>>a;
int u=i, v=i+j;
if(a=='0'){
// v -> u
A[v].set(u);
IN[u].set(v);
}else{
// u -> v
A[u].set(v);
IN[v].set(u);
}
}
}
FOR(_,1,Q){
reply();
}
}
// ?? BFS???????? __ ????=__????? i ??Dis[u][i]=__-1
void bfs(ll u){
bitset<MAXN> vis, q;
vis.reset(); q.reset();
q[u]=1; vis[u]=1;
FOR(__,1,N){
if(q.none()) break;
// ???????????
bitset<MAXN> sum; sum.reset();
for(int i = q._Find_first(); i <= N; i = q._Find_next(i)){
sum |= A[i];
}
// ????????
bitset<MAXN> qq = (~vis) & sum;
// ??????=__?????????? ??-1
for(int i = qq._Find_first(); i <= N; i = qq._Find_next(i)){
Dis[u][i] = __ - 1;
}
vis |= qq;
q = qq;
}
}
void reply(){
ll u,v;
cin>>u>>v;
// k=0????
if(A[u][v]){
cout<<0<<"\n";
return;
}
// k=1???????????? w: u->w && w->v?
if ( (A[u] & IN[v]).any() ){
cout<<1<<"\n";
return;
}
// ????
if(ised[u]){
cout<<Dis[u][v]<<"\n";
return;
}
// ???? u ???
ised[u]=true;
bfs(u);
cout<<Dis[u][v]<<"\n";
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
Solve a;
return 0;
}
/*
*/
```
:::
不判断两次抵达，1309ms
[https://qoj.ac/submission/1410868](https://qoj.ac/submission/1410868)
::: 源代码
```cpp
// by Gospel_rock
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)5e3+10,INF=(ll)1e17+3; // 1e17+3??? 1e18+9???
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;
struct Solve{
vector<bitset<MAXN>> A; // ???OUT?
vector<bitset<MAXN>> IN; // ???IN????????????
vector<vll> Dis; // Dis[u][v] = (???? - 1)???? -1
bitset<MAXN> ised; // ????? u ?? BFS ??
Solve(){
cin>>N>>Q;
A.resize(N+5);
IN.resize(N+5);
Dis.resize(N+5, vll(N+5, -1));
// ??????? i ?? j=i+1..N
FOR(i,1,N){
FOR(j,1,N-i){
char a; cin>>a;
int u=i, v=i+j;
if(a=='0'){
// v -> u
A[v].set(u);
IN[u].set(v);
}else{
// u -> v
A[u].set(v);
IN[v].set(u);
}
}
}
FOR(_,1,Q){
reply();
}
}
// ?? BFS???????? __ ????=__????? i ??Dis[u][i]=__-1
void bfs(ll u){
bitset<MAXN> vis, q;
vis.reset(); q.reset();
q[u]=1; vis[u]=1;
FOR(__,1,N){
if(q.none()) break;
// ???????????
bitset<MAXN> sum; sum.reset();
for(int i = q._Find_first(); i <= N; i = q._Find_next(i)){
sum |= A[i];
}
// ????????
bitset<MAXN> qq = (~vis) & sum;
// ??????=__?????????? ??-1
for(int i = qq._Find_first(); i <= N; i = qq._Find_next(i)){
Dis[u][i] = __ - 1;
}
vis |= qq;
q = qq;
}
}
void reply(){
ll u,v;
cin>>u>>v;
// k=0????
if(A[u][v]){
cout<<0<<"\n";
return;
}
// k=1???????????? w: u->w && w->v?
if ( (A[u] & IN[v]).any() ){
cout<<1<<"\n";
return;
}
// ????
if(ised[u]){
cout<<Dis[u][v]<<"\n";
return;
}
// ???? u ???
ised[u]=true;
bfs(u);
cout<<Dis[u][v]<<"\n";
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--)
Solve a;
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）