Atcoder Beginner 245 G

G - Foreign Friends

题意：给出一个带边权的无向图，每个点有一个颜色，其中还有若干个特殊点。现在要求输出：每个点前往一个颜色与自己不同的特殊点的最短距离

解法：首先不考虑颜色，这个题就是一个魔改的dij，初始将所有特殊点加入队列跑一遍即可。

然后我们考虑颜色，可以将颜色按照二进制位拆开，枚举每一位，将所有在这一位上为0的特殊点加入队列跑一遍dij，并且更新在这一位上为1的点的答案。同样反过来也这么搞一遍

两个颜色不同，则它们至少有一位二进制是不同的（废话

所以任意点距离不同颜色的特殊点之间的最短路一定会被算到。

复杂度 \(O(logn*dij)\)

int n, m, K, L;
int a[maxn], b[maxn];

struct node{
    int t;
    ll dis;
    node(int x, ll y): t(x), dis(y){}
    bool operator >(const node &p)const{
        return dis > p.dis;
    }
};
vector<node> vp[maxn];

ll dis[maxn], ans[maxn];
void dij(int k, int x){
    priority_queue<node, vector<node>, greater<node> > q;
    fill(dis, dis+n+1, 1e18);
    for(int i=0;i<L;i++){
        if((a[b[i]] >> k & 1) == x){
            q.push({b[i], 0});
            dis[b[i]] = 0;
        }
    }
    while(!q.empty()){
        node u = q.top();
        q.pop();
        if(dis[u.t] < u.dis) continue;
        if((a[u.t] >> k & 1) == (x^1)) ans[u.t] = min(ans[u.t], dis[u.t]);
        for(node e: vp[u.t]){
            int v = e.t;
            if(dis[v] > dis[u.t] + e.dis){
                dis[v] = dis[u.t] + e.dis;
                q.emplace(v, dis[v]);
            }
        }
    }
}

void solve(){
    cin >> n >> m >> K >> L;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=0;i<L;i++) cin >> b[i];
    for(int i=1;i<=m;i++){
        int u, v, d;
        cin >> u >> v >> d;
        vp[u].emplace_back(v, d);
        vp[v].emplace_back(u, d);
    }
    fill(ans, ans+n+1, 1e18);
    for(int k=17;k>=0;k--){
        dij(k, 0);
        dij(k, 1);
    }
    for(int i=1;i<=n;i++) cout << (ans[i] > (ll)1e17 ? -1 : ans[i]) << " \n"[i == n];
}