MetronibusDSUeBFS.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
array<vector<int>, 2*MAXN> grafo;
array<int, 2*MAXN> Dist, Marc;
vector<int> pai, sub;

int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int x, int y)
{
    x = find(x); y = find(y);
    if (x == y) return;
    if (sub[x] < sub[y]) swap(x, y);
    pai[y] = x;
    sub[x] += y;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K1, K2, P;
    cin >> N >> K1 >> K2 >> P;

    pai.resize(2*N+1); iota(pai.begin(), pai.end(), 0);
    sub.resize(2*N+1); fill(sub.begin(), sub.end(), 1);

    for (int i = 1; i <= K1; i++)
    {
        int X, Y;
        cin >> X >> Y;
        une(2*X, 2*Y);
    }
    for (int i = 1; i <= K2; i++)
    {
        int X, Y;
        cin >> X >> Y;
        une(2*X+1, 2*Y+1);
    }

    for (int i = 1; i <= N; i++)
    {
        grafo[find(2*i)].push_back(find(2*i+1));
        grafo[find(2*i+1)].push_back(find(2*i));
    }

    int S, F;
    cin >> S >> F;
    queue<int> q;
    Dist.fill(INF);
    Dist[find(2*S)] = Dist[find(2*S+1)] = P;
    Marc[find(2*S)] = Marc[find(2*S+1)] = 1;
    q.push(find(2*S)); q.push(find(2*S+1));

    while (!q.empty())
    {
        int cur = q.front(); q.pop();

        for (auto viz : grafo[cur])
        {
            if (Marc[viz]) continue;
            q.push(viz); Marc[viz] = 1;
            Dist[viz] = Dist[cur] + P;
        }
    }

    int resp = min(Dist[find(2*F)], Dist[find(2*F+1)]);
    cout << (resp == INF ? -1 : resp) << '\n';
}