It solves https://open.kattis.com/problems/bryr

bridges.cpp

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

int const kInf = 1 << 29;

struct edge {
    int node;
    int cost;
};
struct state {
    int node;
    int cost;

    bool operator<(const state& that) const {
        return cost < that.cost;
    }

    bool operator>(const state& that) const {
        return cost > that.cost;
    }
};

int findMinimumCost(vector<vector<edge>> const & graph) {
    unsigned n = graph.size();
    vector<int> distance(n, kInf);
    vector<bool> blocked(n, false);
    priority_queue<state, vector<state>, greater<state>> Q;
    Q.push({0, 0});
    distance[0] = 0;
    while (!Q.empty()) {
        int node = Q.top().node;
        int cost = Q.top().cost;
        Q.pop();
        if (blocked[node]) {
            continue;
        }
        blocked[node] = true;
        for (auto e : graph[node]) {
            int v = e.node;
            if (cost + e.cost < distance[v]) {
                distance[v] = cost + e.cost;
                Q.push({v, cost + e.cost});
            }
        }
    }
    return distance[n-1];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> graph(n);
    for (int idx = 0; idx < m; idx++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a-1].push_back({b - 1, c});
        graph[b-1].push_back({a - 1, c});
    }
    cout << findMinimumCost(graph) << endl;
    return 0;
}