SPFA Shortest Paths

spfa.cc

// ml:std = c++11
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

static int costs[512];
static int weights[512][512];
static int nvert;
static constexpr auto inf = 1000000;

struct PathNode
{
    int dist{inf};
    std::unordered_set<int> prevs;
};
using ShortestPaths = std::vector<PathNode>;

ShortestPaths spfa(int src)
{
    ShortestPaths paths(nvert);
    std::unordered_set<int> pending;

    paths[src].dist = 0;
    pending.insert(src);

    while (pending.size()) {
        auto u = *pending.begin();
        pending.erase(u);

        for (int v=0; v<nvert; v++) {
            auto& dist = paths[v].dist;
            auto dist2 = paths[u].dist + weights[u][v];
            if (dist2 <= dist) {
                if (dist2 < dist) {
                    dist = dist2;
                    paths[v].prevs.clear();
                    pending.insert(v);
                }
                paths[v].prevs.insert(u);
            }
        }
    }

    return paths;
}

static int count = 0;
int count_cost(ShortestPaths const& paths, int u)
{
    if (paths[u].prevs.size() == 0)
        count++;

    int maxcost = 0;
    for (auto prev: paths[u].prevs) {
        auto cost = count_cost(paths, prev);
        if (cost > maxcost) maxcost = cost;
    }
    return maxcost + costs[u];
}

int main()
{
    int nedge, src, dst;
    std::cin >> nvert >> nedge >> src >> dst;

    std::fill_n(&weights[0][0], sizeof(weights)/sizeof(weights[0][0]), inf);

    for (int i=0; i<nvert; i++) std::cin >> costs[i];
    for (int i=0; i<nedge; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        weights[u][v] = weights[v][u] = w;
    }

    auto paths = spfa(src);
    auto cost = count_cost(paths, dst);
    std::cout << count << ' ' << cost << '\n';
}