牛客练习赛67 E. 牛妹游历城市

Description

牛妹现在正在1号点（自己家里），他决定前往n号点（牛妹想去的地方），中途可以多次经过1~n号点。
现在，已知每个点都有个权值 ，如果 & ≠0，则i号点和j号点之间连有一条双向边，权值为。他想要最小化自己的行走距离，但是他计算不出来qaq。相信全牛客最聪明的你一定会吧！

Solution

朴素做法是暴力连所有边，但是边集规模过大，考虑二进制优化，对32个二进制位建立32个虚点，对于每个，如果该二进制位j为1，那么连边权值为 1 << j。（注意虚点到该点的距离为0）
最后跑一个Dijkstra即可，注意 ，不能开 int

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 105;
ll a[N];
bool vis[N];
ll dist[N];
struct Edge {
    int v;
    ll cost;
    Edge(int _v = 0, ll _cost = 0): v(_v), cost(_cost){}
};
vector<Edge> G[N];
struct qnode {
    int v;
    ll cost;
    bool operator < (const qnode &s) const {
        return cost > s.cost;
    }
    qnode(int _v = 0, ll _cost = 0): v(_v), cost(_cost){}
};
void Dijkstra() {
    priority_queue<qnode> q;
    q.push(qnode(1, 0));
    dist[1] = 0;
    while(!q.empty()) {
        qnode now = q.top(); q.pop();
        int u = now.v;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v;
            ll cost = G[u][i].cost;
            if(!vis[v] && dist[v] > dist[u] + cost) {
                dist[v] = dist[u] + cost;
                q.push({v, dist[v]});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i], G[i].clear(), dist[i] = 1e18, vis[i] = false;
        for(int i = n + 1; i <= n + 50; i++) {
            G[i].clear(), dist[i] = 1e18, vis[i] = false;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 32; j++) {
                if(a[i] & (1LL << j)) {
                    G[i].push_back({n + 1 + j, 1LL << j});
                    G[n + 1 + j].push_back({i, 0});
                } 
            }
         }
        Dijkstra();
        if(dist[n] == 1e18) cout << "Impossible\n";
        else cout << dist[n] << "\n";
    }
    return 0;
}