Grafo ponderado:
    0 --4-- 1 --1-- 3
    |       |       |
    2       8       2
    |       |       |
    2 --5-- 4 --6-- 5

Dijkstra a partir de 0:
  dist = [0, ∞, ∞, ∞, ∞, ∞]

  Processa 0 (d=0): relaxa 1(4), 2(2)
  dist = [0, 4, 2, ∞, ∞, ∞]

  Processa 2 (d=2): relaxa 4(2+5=7)
  dist = [0, 4, 2, ∞, 7, ∞]

  Processa 1 (d=4): relaxa 3(4+1=5), 4(4+8=12 > 7, ignora)
  dist = [0, 4, 2, 5, 7, ∞]

  Processa 3 (d=5): relaxa 5(5+2=7)
  dist = [0, 4, 2, 5, 7, 7]

  Processa 4 (d=7): relaxa 5(7+6=13 > 7, ignora)
  Processa 5 (d=7): sem atualizações

  Resultado: [0, 4, 2, 5, 7, 7]

const std = @import("std");
const Allocator = std.mem.Allocator;
const Order = std.math.Order;

const Aresta = struct {
    destino: u32,
    peso: u32,
};

const GrafoPonderado = struct {
    adjacencia: []std.ArrayList(Aresta),
    num_vertices: u32,
    allocator: Allocator,

    pub fn init(allocator: Allocator, n: u32) !GrafoPonderado {
        const adj = try allocator.alloc(std.ArrayList(Aresta), n);
        for (adj) |*lista| lista.* = std.ArrayList(Aresta).init(allocator);
        return .{ .adjacencia = adj, .num_vertices = n, .allocator = allocator };
    }

    pub fn deinit(self: *GrafoPonderado) void {
        for (self.adjacencia) |*l| l.deinit();
        self.allocator.free(self.adjacencia);
    }

    pub fn addAresta(self: *GrafoPonderado, u: u32, v: u32, peso: u32) !void {
        try self.adjacencia[u].append(.{ .destino = v, .peso = peso });
        try self.adjacencia[v].append(.{ .destino = u, .peso = peso });
    }

    pub fn addArestaDirecionada(self: *GrafoPonderado, u: u32, v: u32, peso: u32) !void {
        try self.adjacencia[u].append(.{ .destino = v, .peso = peso });
    }
};

const NoDist = struct {
    vertice: u32,
    distancia: u64,

    fn comparar(_: void, a: NoDist, b: NoDist) Order {
        return std.math.order(a.distancia, b.distancia);
    }
};

/// Algoritmo de Dijkstra — retorna distâncias mínimas e predecessores.
pub fn dijkstra(
    allocator: Allocator,
    grafo: *const GrafoPonderado,
    origem: u32,
) !struct { dist: []u64, pai: []i32 } {
    const n = grafo.num_vertices;
    const INF: u64 = std.math.maxInt(u64);

    const dist = try allocator.alloc(u64, n);
    @memset(dist, INF);

    const pai = try allocator.alloc(i32, n);
    @memset(pai, -1);

    const processado = try allocator.alloc(bool, n);
    defer allocator.free(processado);
    @memset(processado, false);

    // Min-heap (fila de prioridade)
    var heap = std.PriorityQueue(NoDist, void, NoDist.comparar).init(allocator, {});
    defer heap.deinit();

    dist[origem] = 0;
    try heap.add(.{ .vertice = origem, .distancia = 0 });

    while (heap.removeOrNull()) |no| {
        const u = no.vertice;
        if (processado[u]) continue;
        processado[u] = true;

        // Relaxa todas as arestas de u
        for (grafo.adjacencia[u].items) |aresta| {
            const v = aresta.destino;
            const nova_dist = dist[u] + aresta.peso;

            if (nova_dist < dist[v]) {
                dist[v] = nova_dist;
                pai[v] = @intCast(u);
                try heap.add(.{ .vertice = v, .distancia = nova_dist });
            }
        }
    }

    return .{ .dist = dist, .pai = pai };
}

/// Reconstrói o caminho mais curto.
pub fn reconstruirCaminho(allocator: Allocator, pai: []const i32, destino: u32) ![]u32 {
    var caminho = std.ArrayList(u32).init(allocator);
    var atual: i32 = @intCast(destino);
    while (atual != -1) {
        try caminho.insert(0, @intCast(@as(u32, @intCast(atual))));
        atual = pai[@intCast(@as(u32, @intCast(atual)))];
    }
    return caminho.toOwnedSlice();
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var grafo = try GrafoPonderado.init(allocator, 6);
    defer grafo.deinit();

    try grafo.addAresta(0, 1, 4);
    try grafo.addAresta(0, 2, 2);
    try grafo.addAresta(1, 3, 1);
    try grafo.addAresta(1, 4, 8);
    try grafo.addAresta(2, 4, 5);
    try grafo.addAresta(3, 5, 2);
    try grafo.addAresta(4, 5, 6);

    const res = try dijkstra(allocator, &grafo, 0);
    defer allocator.free(res.dist);
    defer allocator.free(res.pai);

    try stdout.print("Distâncias de 0:\n", .{});
    for (res.dist, 0..) |d, i| {
        try stdout.print("  0 → {d}: {d}\n", .{ i, d });
    }

    const caminho = try reconstruirCaminho(allocator, res.pai, 5);
    defer allocator.free(caminho);
    try stdout.print("Caminho 0→5: ", .{});
    for (caminho) |v| try stdout.print("{d} ", .{v});
    try stdout.print("(distância: {d})\n", .{res.dist[5]});
}