提出 #577950

---

ソースコード 拡げる

#include<bits/stdc++.h>

using namespace std;

#define reps(i,f,n) for(int i = f; i <= (n); ++i)
#define rep(i,n) reps(i,0,n-1)
#define rrep(i,n) for(int i=(n)-1; i>=0 ; --i)

#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define eb emplace_back



typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef pair<pii,int> piii;
typedef vector<vector<int>> Graph;

const int INF=3e6;

void dij(Graph &g,int s,vector<pii> &d,vector<int> &val){
  priority_queue<piii,vector<piii>,greater<piii>> que;
  int V=g.size();
  d.resize(V);
  d.resize(V);
  fill(all(d),pii(INF,-1));
  d[s]=pii(0,val[s]);
  que.emplace(d[s],s);
  while(!que.empty()){
    piii p=que.top(); que.pop();
    int v=p.Y;
    if(d[v]<p.X) continue;
    rep(i,g[v].size()){
      if(d[g[v][i]]>pii(d[v].X+1,min(d[v].Y, val[g[v][i]] ))){
	d[g[v][i]]=pii(d[v].X+1,min(d[v].Y, val[g[v][i]] ));
	que.push(piii(d[g[v][i]],g[v][i]));
      }
    }
  }
}

int main(void){
  ios_base::sync_with_stdio(0);
  int n,m,cnt[3];
  cin>>n;
  vector<int> type(n+3),val(n+3,INF);
  iota(all(type),0);
  rep(i,3) cin>>cnt[i];
  int x,y;
  rep(i,3)rep(j,cnt[i]){
    cin>>x; --x;
    type[x]=n+i;
  }
  rep(i,n+3)
    val[type[i]]=min(val[type[i]],i);
  const int N=n+3;
  Graph g(N);
  cin>>m;
  rep(i,m){
    cin>>x>>y;
    --x; --y;
    g[type[x]].eb(type[y]);
    g[type[y]].eb(type[x]);
  }

  vector<pii> d[3];
  rep(i,3)
    dij(g,n+i,d[i],val);
  
  //rep(i,3){rep(j,N)cout<<"("<<d[i][j].X<<","<<d[i][j].Y<<")";cout<<endl;}

  pii re=pii(INF,-1);
  rep(i,N){
    pii tmp=pii(0,INF);
    rep(j,3){
      tmp.X+=d[j][i].X;
      tmp.Y=min(tmp.Y,d[j][i].Y);
    }
    re=min(re,tmp);
  }
  cout<<re.X<<" "<<re.Y+1<<endl;
  return 0;
}

提出情報

ジャッジ結果