一个简单的bfs打表,O(1)查询

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 4e4;
const int mod = 1e9 + 7;
int step[maxn];
int arr[20];
int n,m;
void bfs(){
    memset(step, 1, sizeof(step));
    priority_queue <int> que;
    que.push( step[0] = 0 );
    while(!que.empty()){
        int now = que.top();
        que.pop();
        for(int i = 0; i<n; i++){
            if(step[now^arr[i]] > step[now]+1){
                step[now^arr[i]] = step[now]+1;
                que.push(now^arr[i]);
            }
        }
        for(int i=0; i<17; i++){
            if(step[now^(1<<i)] > step[now]+1){
                step[now^(1<<i)] = step[now]+1;
                que.push(now^(1<<i));
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int T;cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=0; i<n; i++){
            cin>>arr[i];
        }
        bfs();
        int ans=0;
        int x,y;
        for(int i=1; i<=m; i++){
            cin>>x>>y;
            ans=(ans+(step[x^y]*i)%mod)%mod;
        }
        cout<<ans%mod<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注