E

题目大意

给定 个点，第 个点有权值 。如果对于 有 不为 ，那么 间有无向边，边权为 。问从 到 的最短路。

题解

想了一个很憨的做法：依次考虑每一个位，对当前位建立一个新点，设为 。遍历所有点，如果点 满足这一位上为 ，那么连一条从 到 的边，边权为这一位对应的二进制数；再连一条从 到 的边，边权为 。

然后跑 Dijkstra 即可。时间复杂度很高，但居然能过，我也是没想到的。

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
unsigned a[100005];
ll dis[100005 + 50];
priority_queue<pair<int, ll>, vector<pair<int, ll> >, 
    greater<pair<int, ll> > > pq;
int to[6400005], nxt[6400006], at[100005 + 50], cnt;
unsigned w[6400005];
void init(){
    n = read();
    REP(i, 1, n) scanf("%u", &a[i]);
    // build graph
    memset(at, 0, sizeof(at));
    cnt = 0;
    int nn = n;
    for (unsigned t = 1; t > 0; t <<= 1){
        ++n;
        REP(i, 1, nn){
            if (a[i] & t){
                to[++cnt] = n, nxt[cnt] = at[i], w[cnt] = t, at[i] = cnt;
                to[++cnt] = i, nxt[cnt] = at[n], w[cnt] = 0, at[n] = cnt;
            }
        }
    }
}
void solve(){
    memset(dis, 0x3f, sizeof(dis));
    ll lim = dis[1];
    dis[1] = 0;
    pq.push(make_pair(1, 0));
    for (; ; ){
        while (!pq.empty()){
            if (pq.top().second > dis[pq.top().first])
                pq.pop();
            else break;
        }
        if (pq.empty()) break;
        int h = pq.top().first;
        ll dd = pq.top().second;
        pq.pop();
        for (int i = at[h]; i; i = nxt[i]){
            if (dd + w[i] < dis[to[i]])
                dis[to[i]] = dd + w[i], 
                pq.push(make_pair(to[i], dis[to[i]]));
        }
    }

    if (dis[n - 32] == lim){
        printf("Impossible\n");
    }else printf("%lld\n", dis[n - 32]);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}