bandwidth 2

gistfile1.txt

#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <iostream>

class Computer;

class Link {
public:
    int bw;
    int src;
    Computer* dst;
};

class Computer {
public:
    int id;
    // Start link index.
    int link_idx;
    // The fastest link bandwidth found yet to this computer from origin.
    int bw = 0;
};

class Marker {
public:
    // Bandwidth when marker was inserted.
    int bw;
    // Computer of marker.
    Computer* comp;
};

int main(int argc, char* argv[]) {
    // Read input.
    std::ios_base::sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    std::vector<Computer> comps(n);
    std::vector<Link> links(m * 2);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;
        links[i * 2 + 0] = {.bw = c, .src = a, .dst = &comps[b]};
        links[i * 2 + 1] = {.bw = c, .src = b, .dst = &comps[a]};
    }
    std::sort(links.begin(), links.end(), [](const Link& a, const Link& b) -> bool {
        return a.src != b.src? a.src < b.src: a.bw > b.bw;
    });
    for (int prev_src = -1, i = 0; i < links.size(); i++) {
        auto& l = links[i];
        if (l.src != prev_src) {
            auto& comp = comps[l.src];
            comp.id = l.src;
            comp.link_idx = i;
            prev_src = l.src;
        }
    }
    // Select arbitrary vertex where we start bandwidth search.
    // Localhost has infinite bandwidth.
    auto& comp0 = comps[0];
    comp0.bw = INT_MAX;
    // Max heap for djikstra state. Since the vector only has one element it
    // satisfies the heap property per definition.
    std::vector<Marker> heap({{
        .bw = comp0.bw,
        .comp = &comp0,
    }});
    auto cmp_marker = [](const Marker& a, const Marker& b) -> bool {
        return a.bw < b.bw;
    };
    // Start search.
    int min_bw = 0;
    while (heap.size() > 0) {
        // We search from the vertex (computer) with the highest bandwidth.
        std::pop_heap(heap.begin(), heap.end(), cmp_marker);
        auto mrk = heap.back();
        heap.pop_back();
        // Filter out non valid markers.
        auto& comp = *mrk.comp;
        if (mrk.bw != comp.bw) {
            continue;
        }
        // Have vertex (computer) with higest bandwidth, go through links.
        min_bw = comp.bw;
        for (int i = comp.link_idx; i < links.size(); i++) {
            auto& l = links[i];
            if (l.src != comp.id) {
                break;
            }
            int bw = std::min(comp.bw, l.bw);
            auto& dst = *l.dst;
            if (bw > dst.bw) {
                // Insert new marker.
                dst.bw = bw;
                heap.push_back({.bw = bw, .comp = &dst});
                std::push_heap(heap.begin(), heap.end(), cmp_marker);
            }
        }
    }
    // Print the computer with the lowest bandwidth.
    // The heap property and min function ensures that it is always searched last.
    std::cout << min_bw;
    exit(0);
}