E 牛妹游历城市

题目地址：

https://ac.nowcoder.com/acm/contest/6885/E

基本思路：

比较容易让人想到最短路,
但是如果直接建图跑,很明显会超时,所以我们考虑重新建图,
我们将每一个二进制位设置为个虚点，将所有这一二进制位为的数都连向这个虚点,
并且将入边的权值设为这个二进制位的基数,出边权值设为,
具体什么意思,我们参考下面的例子:
考虑,这两个数,它们转换为二进制为：和，我们将顶点标下号,
这两个数的点我们设为和,二进制第一位我们设为，第二位设为,依次类推，那么我们有如下这幅图：
图片说明
(不太会用软件,标上边权就重叠了，所以没弄，可以自己画一下)
然后我们看,,这两个数字实际上是被二进制第一位和第三位都连着了,
但是由于二进制第一位的边权明显是小于第三位的,那么在实际最短路中,肯定只会走这个更短的边权,
这也就是的效果,那么就能证明这样的建图是正确的了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
int a[maxn], dis[maxn];
struct edge {
    int to, next,w;
}edge[maxn];
int head[maxn], cnt;
void add_edge(int u, int v, int w) {
  edge[++cnt] = {v, head[u], w};
  head[u] = cnt;
  edge[++cnt] = {u, head[v], 0};
  head[v] = cnt;
}
int n;
bool vis[maxn];
void dijkstra() {
  for (int i = 1; i <= n + 33; i++) dis[i] = INF, vis[i] = false;
  dis[1] = 0;
  priority_queue<pii, vector<pii >, greater<> > q;
  q.push(mp(0, 1));
  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].to;
      if (dis[v] > dis[u] + edge[i].w) {
        dis[v] = dis[u] + edge[i].w;
        q.push(mp(dis[v], v));
      }
    }
  }
}
signed main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    cnt = 0, mset(head, -1);
    for (int i = 0; i < 33; i++) {
      for (int j = 1; j <= n; j++) {
        if ((a[j] >> i) & 1) {
          add_edge(j, i + n + 1, 1ll << i);
        }
      }
    }
    dijkstra();
    if (dis[n] == INF) cout << "Impossible" << endl;
    else cout << dis[n] << endl;
  }
  return 0;
}