我欲乘风归去，又恐天上下雨。高处不撑伞。
B. 最短路
http://222.180.160.110:1024/contest/3459/problem/2
非常直白的标题让我在点进去之前认为这是一个板子。我错了。
如果我们真的按照题目所说连边，那么只需要整个数列的值全部相同，就会存在 \(n^2\) 条边，不管是时间还是空间都会起飞。
我们发现两个点之间，至少需要一个公有的二进制位才能相连。那假如，我们把所有二进制位建虚点，并将点与其拥有的二进制位相连呢？
因为点与点之间没有直接连边，二进制位与二进制位之间也没有直接连边，它会变成一个二分图，其边数最多为 \(31\times n\)。
如何处理边权？考虑两个数，他们途径公有二进制位连边，边权应为两个点的权值之和。那这就很明显了，我们只需将一个点和其拥有的二进制位间连一条权值为该点数值的边即可。
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 1e5 + 5;
#define mkp std::make_pair
using pii = std::pair<int, int>;
struct _ {
int v, w;
_() {}
_(int v1, int w1) {
v = v1, w = w1;
}
};
int n;
bool vis[maxn];
int a[maxn], dis[maxn];
std::vector<_> g[maxn];
std::priority_queue<pii> q;
inline void add(int x, int y, int w) {
g[x].push_back(_(y, w));
return;
}
inline void Dijk(int s) {
for (int i = 2; i <= n + 32; ++i)
dis[i] = inf;
q.push(mkp(0, s));
while (!q.empty()) {
int f = q.top().second;
q.pop();
if (vis[f])
continue;
vis[f] = 1;
for (auto i : g[f]) {
if (dis[i.v] > dis[f] + i.w) {
dis[i.v] = dis[f] + i.w;
q.push(mkp(-dis[i.v], i.v));
}
}
}
return;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]);
for (int j = 0; j <= 31; ++j) {
if (a[i] & (1ll << j)) {
add(i, j + n + 1, a[i]);
add(j + n + 1, i, a[i]);
}
}
}
Dijk(1);
for (int i = 1; i <= n; ++i) {
if (dis[i] == inf)
print(-1, ' ');
else print(dis[i], ' ');
}
return 0;
}
} // namespace XSC062