前言
学长博客划水，抄题解，差评。
于是我来重新写一篇正常的题解，虽然解法跟标程不一样，但是复杂度是一样的。
题面
题目描述
在比特镇一共有(n)个街区，编号依次为(1)到(n)，它们之间通过若干条单向道路连接。
比特镇的交通系统极具特色，除了(m)条单向道路之外，每个街区还有一个编码(val_i)，
不同街区可能拥有相同的编码。如果(val_i and val_j = val_j)(博主注:and这里指位与，即C++中的&)，
即(val_i)在二进制下与(val_j)做与运算等于(val_j)，那么也会存在一条额外的从(i)出发到(j)的单向道路。
(Byteasar)现在位于(1)号街区，他想知道通过这些道路到达每一个街区最少需要多少时间。
因为比特镇的交通十分发达，你可以认为通过每条道路都只需要(1)单位时间。
输入
第一行包含两个正整数(n,m)，表示街区的总数以及道路的总数。
第二行包含(n)个正整数(val_1,val_2,dots,val_n)，分别表示每个街区的编码。
接下来(m)行，每行包含两个正整数(u_i,v_i)，表示一条单向道路，起点为(u_i)，终点为(v_i)。
输出
输出(n)行，每行一个整数，其中第(i)行输出到达第(i)个街区的最少时间，如果无法到达则输出(-1)。
题解
这是一道好题，主要难点在于建图，
一开始我想到暴力连边，然后跑dijkstra。
像这样(注意，下面的代码是会TLE的):
#include <cstdio>
#include <set>
using namespace std;
int read(){
int x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
struct Edge{
int to, next;
} edges[600005];
int head[200005], edge_num;
void addEdge(int from, int to){
edges[++edge_num] = (Edge){to, head[from]};
head[from] = edge_num;
}
long long dist[200005];
int val[200005];
set< pair<long long, int> > que;
int n, m;
void dijkstra(int st){
que.clear();
for (int i = 1; i <= n; ++i)
dist[i] = -1;
dist[st] = 0;
pair<long long, int> cur; cur.first = 0, cur.second = st;
que.insert(cur); int u, v;
while (!que.empty()){
u = (*que.begin()).second; que.erase(que.begin());
for (int c_e = head[u]; c_e; c_e = edges[c_e].next){
v = edges[c_e].to;
if (dist[v] == -1 || dist[u] + 1 < dist[v]){
que.erase(make_pair(dist[v], v));
dist[v] = dist[u] + 1;
que.insert(make_pair(dist[v], v));
}
}
}
}
int main(){
freopen("walk.in", "r", stdin);
freopen("walk.out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= n; ++i) val[i] = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if ((val[i] & val[j]) == val[j])
addEdge(i, j);
for (int i = 1; i <= m; ++i){
int u = read(), v = read();
addEdge(u, v);
}
dijkstra(1);
for (int i = 1; i <= n; ++i)
printf("%lld
", dist[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
然后突然发现，边权为1，为什么要跑dijkstra，QAQ。
于是换成了一个BFS。(博主太蠢了...)
但是建边还是会TLE。
于是我们想到，如果把每个点的val也当做一个点，然后将每个点练到val，权为0；每个val连会点，权为1。
然后接着在val之间建边权为0的边即可。
但是val之间的边要是预先处理，那么铁定MLE(边太多了)。
但是我们发现，每个点肯定只会访问一次，那么不如在BFS的时候枚举找到能够去的val点。
然后我们进一步发现如果每次val点搜到所有它能去的点，那么肯TLE，但是我们发现，由于权为0，不如只连在二进制差一位的点，即可(由只差一位的点继续去更新差两、三...位的点)。
然后就解决了，还有一个问题就是有的边权为0，有的边权为1，普通的BFS貌似会崩，但是这种边权我们一看就知道需要用到双端队列BFS。
如果是权为0的边，那么把到达的点插入队首，否则插入队尾，正确性显然，仍然符合BFS的更新规则。
代码
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
const int MAXN = (1 << 20);
int read(){
int x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
struct Edge{
int to, next; bool val;
} edges[5000005];
int head[2000005], edge_num;
int val[2000005];
long long dist[2000005];
void addEdge(int from, int to, bool val){
edges[++edge_num] = (Edge){to, head[from], val};
head[from] = edge_num;
}
deque< pair<int, int> > que;
int vis[2000005];
void BFS(){
dist[1 + MAXN] = 0;
que.clear();
que.push_back(make_pair(1 + MAXN, 0)); vis[1 + MAXN] = 1;
int u, v;
while (!que.empty()){
u = que.front().first, dist[u] = que.front().second, que.pop_front();
if (u <= MAXN){
for (int i = 0; i <= 20; ++i)
if (((1 << i) & u) && !vis[u ^ (1 << i)])
que.push_front(make_pair(u ^ (1 << i), dist[u])), vis[u ^ (1 << i)] = 1;
if (!vis[0])
que.push_front(make_pair(0, dist[u])), vis[0] = 1;
}
for (int c_e = head[u]; c_e; c_e = edges[c_e].next){
v = edges[c_e].to;
if (!vis[v]){
vis[v] = 1;
if (!edges[c_e].val)
que.push_front(make_pair(v, dist[u]));
else
que.push_back(make_pair(v, dist[u] + 1));
}
}
}
}
int main(){
int n = read(), m = read();
for (int i = 1; i <= n; ++i){
val[i] = read();
addEdge(i + MAXN, val[i], 0), addEdge(val[i], i + MAXN, 1);
}
for (int i = 1; i <= m; ++i){
int u = read() + MAXN, v = read() + MAXN;
addEdge(u, v, 1);
}
for (int i = 0; i <= MAXN + n; ++i)
dist[i] = -1;
BFS();
for (int i = MAXN + 1; i <= MAXN + n; ++i)
printf("%lld
", dist[i]);
return 0;
}
后记
博主很菜，也没怎么卡常，但是效率是十分优秀的。
如果您想了解更多解法（BFS+DFS枚举子集(标算打法)，dijkstra）请去Chhokmah的博客。