Skip to content

Instantly share code, notes, and snippets.

@cjxgm

cjxgm/spfa.cc

Created March 2, 2017 17:02
Show Gist options
  • Save cjxgm/17a99f4f823a8631855af5a0ae7aa33f to your computer and use it in GitHub Desktop.
Save cjxgm/17a99f4f823a8631855af5a0ae7aa33f to your computer and use it in GitHub Desktop.
Download ZIP
SPFA Shortest Paths
Raw
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';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment