Spaces:
Sleeping
Sleeping
File size: 2,761 Bytes
bf9c466 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | // 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;
}
|