MetronibusBFS01.cpp

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K1, K2, P;
    cin >> N >> K1 >> K2 >> P;
    for (int i = 1; i <= K1; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[2*X].emplace_back(2*Y, 0);
        grafo[2*Y].emplace_back(2*X, 0);
    }
    for (int i = 1; i <= K2; i++)
    {
        int X, Y;
        cin >> X >> Y;
        grafo[2*X + 1].emplace_back(2*Y + 1, 0);
        grafo[2*Y + 1].emplace_back(2*X + 1, 0);
    }

    for (int i = 1; i <= N; i++)
    {
        grafo[2*i].emplace_back(2*i + 1, P);
        grafo[2*i + 1].emplace_back(2*i, P);
    }

    int S, F;
    cin >> S >> F;
    deque<int> q;
    Dist.fill(INF);
    Dist[2*S] = Dist[2*S + 1] = P;
    q.push_back(2*S); q.push_back(2*S + 1);

    while (!q.empty())
    {
        int cur = q.front(); q.pop_front();
        if (Marc[cur]) continue;
        Marc[cur] = 1;

        for (auto [viz, p] : grafo[cur])
        {
            if (Marc[viz]) continue;
            if (Dist[viz] <= Dist[cur] + p) continue;
            if (p == 0) Dist[viz] = Dist[cur], q.push_front(viz);
            else Dist[viz] = Dist[cur] + p, q.push_back(viz);
        }
    }

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