Problem: Example

Input

4 2 1 1
1 2
3
4
3
1 2
2 4
3 4


Output

2 1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

struct state{
  int pos,bit,cost;
  bool operator < ( const state s )const{
    return cost > s.cost;
  }
};

int N,M,A,B,C;
priority_queue< state > Q;
vector<int> G[100005];

int d[100005][(1<<3)];
int f[100005];
int t[100005];

int main(){
  for(int i=0;i<100005;i++)
    for(int j=0;j<(1<<3);j++)
      d[i][j]=1e9;

  scanf("%d %d %d %d",&N,&A,&B,&C);

  memset(f,-1,sizeof(f));
  for(int i=0;i<A;i++){
    int a;
    scanf("%d",&a);
    a--;

    G[100001].push_back(a);
    G[a].push_back(100001);
    
    f[a]=0;
    Q.push( (state){ a, 1 , 0 } );
    d[a][1]=0;
  }
  for(int i=0;i<B;i++){
    int b;
    scanf("%d",&b);
    b--;

    G[100002].push_back(b);
    G[b].push_back(100002);
    
    f[b]=1;
    Q.push( (state){ b,2,0 } );
    d[b][2]=0;
  }
  for(int i=0;i<C;i++){
    int c;
    scanf("%d",&c);
    c--;

    G[100003].push_back(c);
    G[c].push_back(100003);
    
    f[c]=2;
    Q.push( (state){c,4,0} );
    d[c][4]=0;
  }
  
  cin>>M;
  for(int i=0;i<M;i++){
    int x,y;
    scanf("%d %d",&x,&y);
    x--,y--;
    G[x].push_back(y);
    G[y].push_back(x);
    
  }
  while(!Q.empty()){
    state s=Q.top();Q.pop();
    int pos=s.pos;
    int bit=s.bit;
    int cost=s.cost;
    if( d[pos][bit] < cost )continue;
    t[pos]|=bit;
    
    for(int bb=t[pos];bb>0;bb=(bb-1)&t[pos]){
      for(int B=bb;B>0;B=(B-1)&bb){
        int ncost=d[pos][ (B&bb) ] + d[pos][ bb-(B&bb) ];
        if(d[pos][bb]>ncost){
          Q.push( (state){pos,bb,ncost} );
          d[pos][bb]=ncost;
        }
      }
    }

    for(int to:G[pos]){
      int ncost=cost+1;
      
      if( f[to]!=-1 && f[to]==f[pos]){
        ncost=cost;
      }else if(to>100000||pos>100000){
        ncost=cost;
      }
      
      if(d[to][bit]>ncost){
        d[to][bit]=ncost;
        Q.push( (state){to,bit,ncost} );
      }
    }
  }
  int ans=1e9,id;
  for(int i=0;i<N;i++){
    if( ans > d[i][7] ){
      ans=d[i][7];
      id=i;
    }
  }
  cout<<ans<<' '<<id+1<<endl;
  
  return 0;
}