tasks/shortest/source.cpp

// tasks/shortest/source.cpp
// Dijkstra's algorithm in C++ using std::priority_queue.
// Agents must migrate this to Rust (no HashMap, no unsafe, Aeneas-safe).
//
// Key invariants:
//   - Non-negative edge weights
//   - Unreachable nodes represented as None (Rust) / u64::MAX sentinel (C++)
//   - Input: edge list (from, to, weight) as Vec<(u64,u64,u64)>
//   - Output: Vec<Option<u64>> of length n

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cstdint>
#include <optional>

using u64 = uint64_t;
static constexpr u64 INF = std::numeric_limits<u64>::max();

struct Edge { u64 to, weight; };
using Graph = std::vector<std::vector<Edge>>;

// Build adjacency list from edge triples
Graph build_graph(const std::vector<std::tuple<u64,u64,u64>>& edges, size_t n) {
    Graph g(n);
    for (auto& [from, to, w] : edges) {
        if (from < n && to < n) g[from].push_back({to, w});
    }
    return g;
}

// Single-source shortest paths. Returns INF for unreachable nodes.
std::vector<u64> dijkstra_raw(const Graph& g, size_t src) {
    size_t n = g.size();
    std::vector<u64> dist(n, INF);
    dist[src] = 0;
    // min-heap: (dist, node)
    std::priority_queue<std::pair<u64,u64>,
                        std::vector<std::pair<u64,u64>>,
                        std::greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto& [v, w] : g[u]) {
            u64 nd = dist[u] + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    return dist;
}

// Public API: returns Option<u64> per node (None = unreachable)
std::vector<std::optional<u64>> dijkstra(
    const std::vector<std::tuple<u64,u64,u64>>& edges, size_t n, size_t src)
{
    Graph g = build_graph(edges, n);
    auto raw = dijkstra_raw(g, src);
    std::vector<std::optional<u64>> result(n);
    for (size_t i = 0; i < n; i++)
        result[i] = (raw[i] == INF) ? std::nullopt : std::optional<u64>(raw[i]);
    return result;
}

// Shortest distance from src to dst (None if unreachable)
std::optional<u64> shortest_dist(
    const std::vector<std::tuple<u64,u64,u64>>& edges,
    size_t n, size_t src, size_t dst)
{
    if (dst >= n) return std::nullopt;
    auto dists = dijkstra(edges, n, src);
    return dists[dst];
}

int main() {
    std::vector<std::tuple<u64,u64,u64>> edges = {{0,1,5},{1,2,3}};
    auto d = shortest_dist(edges, 3, 0, 2);
    std::cout << "dist(0,2) = " << (d ? std::to_string(*d) : "none") << "\n";  // 8
    auto d2 = shortest_dist(edges, 3, 0, 0);
    std::cout << "dist(0,0) = " << (d2 ? std::to_string(*d2) : "none") << "\n"; // 0
    return 0;
}