GalaxyOJ-1000 (缩点+最短路)

题目

http://www.gdfzoj.com/oj/contest/247/problems/3

分析

• 对于前四个数据，直接暴力建图再 SPFA 一下最短路即可。
• 分析一下，对于后面的数据，主要是建图时“特殊边”（就是根据与运算得出的边）建的时候需要平方的复杂度，优化一下这里即可。
• 可以考虑弄完一个点的 dis[] 之后，直接把它能通过“特殊边”到的点都更新一次。
• 由于边长都为1，所以对于每个点肯定是第一次更新的值是最小的，弄“点权范围”个 vector 存下点权为它的点的编号，每次讨论时 dfs 一下把它能一步到的点更新一下即可。（之前更新过的就不用换了）

程序

#include <cstdio>
#include <cstring>
#include <vector>
#define Add(x,y) (to[++num]=head[x],head[x]=num,V[num]=y)
#define For(x) for(int h=head[x],o=V[h]; h; o=V[h=to[h]])
using namespace std;
int head[200005],to[300005],V[300005],num;
int q[2000000],vis[200005],f[1100000],l,r;
int n,m,val[200005],dis[200005];
vector <int> a[1100000];

void dfs(int x,int ds){     //从某个 权值为 x 的点 通过特殊路到的点，dis=ds 
    if (f[x]) return;
    f[x]=1;
    for (int i=20; i>=0; i--) if (x&(1<<i)) dfs(x^(1<<i),ds);
    if (!a[x].empty()) for (int i=0; i<a[x].size(); i++){
        int o=a[x][i];
        if (vis[o]) continue;
        vis[o]=1;
        dis[o]=ds;
        q[++r]=o;
    }
}

int main(){
    freopen("1.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) scanf("%d",val+i),a[val[i]].push_back(i);
    for (int i=1,x,y; i<=m; i++) scanf("%d%d",&x,&y),Add(x,y);  
    memset(dis,0x7f,sizeof(dis)); dis[1]=0;
    for (q[l=r=0]=vis[1]=1; l<=r; l++){
        int u=q[l];
        For(u) if (!vis[o]){
            vis[o]=1;
            dis[o]=dis[u]+1;
            q[++r]=o;
        }
        dfs(val[u],dis[u]+1);       //讨论一下 u 能连到的特殊路 
    }
    for (int i=1; i<=n; i++)
        printf("%d\n",dis[i]>n?-1:dis[i]);
}