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 <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
typedef long long int lli;
const int inf = 1e9;

vector<lli> shortest_path(int from, vector<vector<pair<int,lli>>> &graph){
    int n = graph.size();
    vector<lli> mincost(n, inf);
    mincost[from] = 0;
    priority_queue<pair<lli,int>> wait;
    wait.push({0LL, from});
    while(!wait.empty()){
        lli cost = -wait.top().first;
        int pos = wait.top().second;
        wait.pop();
        if(cost > mincost[pos]) continue;
        for(auto next: graph[pos]){
            lli ncost = cost + next.second;
            int npos = next.first;
            if(ncost < mincost[npos]){
                mincost[npos] = ncost;
                wait.push({-ncost, npos});
            }
        }
    }
    return mincost;
}

int main(){
    int n,s[3];
    cin >> n >> s[0] >> s[1] >> s[2];
    vector<int> sh(3, inf);
    vector<int> col(n, -1);
    for(int i=0; i<3; i++){
        for(int j=0; j<s[i]; j++){
            int a;
            cin >> a;
            a--;
            col[a] = i;
            sh[i] = min(sh[i], a);
        }
    }
    int m;
    cin >> m;
    vector<vector<pair<int, lli>>> g(n);
    for(int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        if(col[a] != -1) a = sh[col[a]];
        if(col[b] != -1) b = sh[col[b]];
        g[a].emplace_back(b, 1);
        g[b].emplace_back(a, 1);
    }
    vector<vector<lli>> mincost(3);
    for(int i=0; i<3; i++){
        mincost[i] = shortest_path(sh[i], g);
    }

    pair<lli, int> ans(inf, n);
    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<2; k++){
                lli tmpcost = mincost[j][i] +mincost[(j+1)%3][i] +mincost[(j+2)%3][sh[(j+k)%3]];
                ans = min(ans, {tmpcost, i});
            }
        }
        lli tmpcost = mincost[0][i] +mincost[1][i] +mincost[2][i];
        ans = min(ans, {tmpcost, i});
    }
    for(int i=0; i<n; i++){
        lli tmpcost = mincost[0][i] +mincost[1][i] +mincost[2][i];
        if(tmpcost > ans.first) continue;
        auto from_i = shortest_path(i, g);
        for(int j=0; j<ans.second; j++){
            for(int k=0; k<3; k++){
                if(mincost[k][i] == mincost[k][j] +from_i[j]){
                    ans.second = j;
                    break;
                }
            }
        }
    }
    cout << ans.first << " " << ans.second +1 << endl;
    return 0;
}