题解 | #最短路#

首先可以发现，如果有a,b,c三个点，且a向b和c连边，b向c连边，
那么此时a直接走到c一定比以b作为中间结点更优

开始将维护数组v[i],v[i]里面存了所有二进制第i位为1的数的编号
那么可以构造一个DAG，比如刚开始的时候枚举a[1]的所有的1位，然后直接把v[i]里面的所有点的最短路更新为1到它的距离。然后让新的点入优先队列。
维护一个优先队列让距离小的优先更新，而每个v[i]最多被访问一次，即每个点到1的最多距离最多只会被更新一次

#include <bits/stdc++.h>
#define N 100010
#define ll long long
//#define Re register
#define mo 998244353
#define squ(x) ((x)*(x))
#define db double
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define drep(i,r,l)for(int i=r;i>=l;--i)
#define pb push_back
using namespace std;

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int a[N];
vector<int> v[34];
ll dis[N];
bool vis[34];
#define Pa pair<ll,int>
#define mp make_pair
priority_queue<Pa, vector<Pa>, greater<Pa> > q;
bool cmp(int i, int j) {
    return a[i] < a[j];
}
int main() {
    int n = read();
    rep(i, 1, n) {
        dis[i] = -1;
        a[i] = read();
        rep(p, 0, 30)if ((a[i] >> p) & 1)v[p].pb(i);
    }
    rep(p, 0, 30)sort(v[p].begin(), v[p].end(), cmp);
    dis[1] = 0;
    q.push(mp(a[1], 1));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        rep(p, 0, 30) {
            if ((a[u] >> p) & 1) {
                if (vis[p])continue;
                vis[p] = 1;
                for (int &x : v[p])
                {
                    if (dis[x] != -1)continue;
                    dis[x] = dis[u] + a[u] + a[x];
                    q.push(mp(dis[x] + a[x], x));
                }
            }
        }
    }
    rep(i, 1, n)printf("%lld ", dis[i]);
    return 0;
}