Solution for lets meet: https://open.kattis.com/problems/letsmeet

letsmeet.cpp

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

namespace std {
    template<typename S1, typename S2> struct hash<pair<S1, S2>>
    {
        size_t operator()(pair<S1, S2> const& p) const noexcept
        {
            size_t const h1 ( std::hash<S1>{}(p.first) );
            size_t const h2 ( std::hash<S2>{}(p.second) );
            return h1 * 100 + h2;
        }
    };
}

int
main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int s, t;
    cin >> s >> t;

    using States = unordered_map<pair<int, int>, double>;
    States states = { { make_pair(s, t), 1.0 } };
    double exp = 0;
    if (adj[s].size() == 0 or adj[t].size() == 0 or s == t) {
        if (s == t)
            cout << 0 << endl;
        else
            cout << "never meet" << endl;
        return 0;
    }

    double steps = 0;
    for (;;) {
        auto oldexp = exp;
        States nstates;
        double mprob = 0.0;
        // print "step", steps, "states", states, "exp", exp
        double live = 0;
        for (auto [u, p] : states) {
            auto [au, bu] = u;
            double pa = 1.0/adj[au].size();
            double pb = 1.0/adj[bu].size();
            for (auto av : adj[au])
                for (auto bv : adj[bu]) {
                    auto pp = pa * pb * p;
                    if (av == bv)
                        mprob += pp;
                    else {
                        live += pp;
                        nstates[{av, bv}] += pp;
                    }
                }
        }

        steps += 1;
        swap(states, nstates);
        exp += mprob * steps;
        
        if (steps > 500 and exp == 0 or live < 1e-8)
            break;
    }

    if (exp == 0)
        cout << "never meet" << endl;
    else
        cout << setprecision(15) << exp << endl;
}