もうちょっと抽象化したDijkstra

template <class Dist, class Key, class Delta>  // Delta: Key from, (Key to, Dist d -> void) update -> void
std::map<Key, Dist> dijkstra(Key s, Delta delta) {
    std::map<Key, Dist> dist;
    using P = std::pair<Dist, Key>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> q;
    q.push({dist[s] = Dist(), s});
    while (!q.empty()) {
        std::pair<Dist, Key> p = q.top();
        q.pop();
        if (dist[p.second] < p.first) continue;
        delta(p.second, [&](Key to, Dist d) -> void {
            if (dist.count(to) && dist[to] <= p.first + d) return;
            q.push({dist[to] = p.first + d, to});
        });
    }
    return dist;
}

signed main() {
    Int n, m, r;
    std::cin >> n >> m >> r;
    struct Edge {
        Int to, cost;
    };
    std::vector<std::vector<Edge>> g(n);
    REP(i, m) {
        Int s, t, d;
        std::cin >> s >> t >> d;
        g[s].push_back({t, d});
    }
    auto delta = [&](Int from, auto update) -> void {
        for (Edge& edge : g[from]) {
            update(edge.to, edge.cost);
        }
    };
    auto dist = dijkstra<Int>(r, delta);
    REP(i, n) {
        if (dist.count(i)) {
            std::cout << dist[i] << "\n";
        } else {
            std::cout << "INF\n";
        }
    }
}

bool is_palindrome(const std::string& s) { return s == std::string(s.rbegin(), s.rend()); }
const Int INF = 1e18;
const std::string dummy = "01";
signed main() {
    Int n;
    std::cin >> n;
    auto ss = make_vec<std::string>(2, n, "");
    std::vector<Int> c(n);
    REP(i, n) std::cin >> ss[0][i] >> c[i], ss[1][i] = std::string(RALL(ss[0][i]));
    using Key = std::pair<std::string, bool>;
    auto delta = [&](Key from, auto update) -> void {
        REP(i, n) {
            std::string s = from.first == dummy ? "" : from.first;
            std::string t = ss[!from.second][i];
            bool nxt_b = from.second ^ (s.size() < t.size());
            if (s > t) std::swap(s, t);
            if (s != t.substr(0, s.size())) continue;
            std::string nxt_s = t.substr(s.size(), t.size() - s.size());
            update(Key{nxt_s, nxt_b}, c[i]);
        }
    };
    Key s = {dummy, 0};
    auto res = dijkstra<Int>(s, delta);
    Int ans = INF;
    for (auto& p : res) {
        if (is_palindrome(p.first.first)) chmin(ans, p.second);
    }
    std::cout << (ans == INF ? -1 : ans) << std::endl;
}