UVa 12878

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
#include <queue>
#include <set>
#include <array>

using namespace std;

struct Edge
{
    Edge() {};
    Edge(int _id, int _weight, int _from):
    id(_id), weight(_weight), from(_from) {}
    int id;
    int weight;
    int from;
    bool operator<(const Edge& other) const {
        return weight > other.weight;
    }
};

const int NEVER_DISCOVER = -1;
const int INFTY = 1000*1000*1000;

const int nbNodesMax = 10*1000 + 1;
array<int, nbNodesMax> closed_set;
array<set<int>, nbNodesMax> comeFrom;
array<bool, nbNodesMax> seen;
using Node = vector<Edge>;
using Graph = array<Node, nbNodesMax>;
Graph graph;

int dfs(const Edge& edge) {
    int node = edge.id;
    int seum = edge.weight;
    if (seen[node])
        return seum;
    seen[node] = true;
    for (const auto& edge : graph[node]) {
        if (comeFrom[node].find(edge.from) != end(comeFrom[node])) {
            seum += dfs(edge);
        }
    }
    return seum;
}

int
dijkstra(int departure, int arrival)
{
    priority_queue<Edge> openset;
    openset.push(Edge(departure, 0, -1));

    for (auto& from : comeFrom)
        from.clear();

    closed_set.fill(NEVER_DISCOVER);

    while (!openset.empty())
    {
        Edge current = openset.top();
        openset.pop();

        if (closed_set[current.id] != NEVER_DISCOVER
            && current.weight > closed_set[current.id]) {
            break ;
        }

        if (closed_set[current.id] != NEVER_DISCOVER
            && closed_set[current.id] < current.weight)
            continue ;
        closed_set[current.id] = current.weight;
        comeFrom[current.id].insert(current.from);

        for (auto neighbour : graph[current.id]) {
            int newWeight = neighbour.weight + current.weight;
            if (closed_set[neighbour.id] == NEVER_DISCOVER
            || newWeight <= closed_set[neighbour.id]) {
                closed_set[neighbour.id] = newWeight;
                Edge edge(neighbour.id, newWeight, neighbour.from);
                openset.push(edge);
            }
        }
    }

    seen.fill(false);
    return 2*dfs(Edge(arrival, 0, -2));
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int nbNodes, nbEdges;
    while (cin >> nbNodes >> nbEdges) {
        for (auto& node : graph)
            node.clear();
        for (int edge = 0; edge < nbEdges; ++edge)
        {
            int departure, arrival, weight;
            cin >> departure >> arrival >> weight;
            graph[departure].emplace_back(arrival, weight, edge);
            graph[arrival].emplace_back(departure, weight, edge);
        }

        cout << dijkstra(0, nbNodes-1) << "\n";
    }
}