Grafo ponderado não-direcionado:

    0 --4-- 1 --2-- 2
    |       |       |
    8       3       7
    |       |       |
    3 --1-- 4 --6-- 5

Dijkstra a partir de 0:
  0: dist=0
  1: dist=4  (via 0->1)
  4: dist=7  (via 0->1->4)
  3: dist=8  (via 0->3 ou 0->1->4->3)
  2: dist=6  (via 0->1->2)
  5: dist=13 (via 0->1->4->5)

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

/// Grafo ponderado com lista de adjacência.
pub fn GrafoPonderado(comptime direcionado: bool) type {
    return struct {
        const Self = @This();

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

        adjacencias: []std.ArrayList(Aresta),
        num_vertices: u32,
        num_arestas: u32,
        allocator: Allocator,

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

        pub fn deinit(self: *Self) void {
            for (self.adjacencias) |*lista| {
                lista.deinit();
            }
            self.allocator.free(self.adjacencias);
        }

        /// Adiciona aresta com peso.
        pub fn adicionarAresta(self: *Self, u: u32, v: u32, peso: i64) !void {
            try self.adjacencias[u].append(.{ .destino = v, .peso = peso });
            if (!direcionado) {
                try self.adjacencias[v].append(.{ .destino = u, .peso = peso });
            }
            self.num_arestas += 1;
        }

        /// Dijkstra — caminho mínimo (pesos não-negativos).
        /// Retorna distâncias e predecessores.
        pub fn dijkstra(self: *const Self, origem: u32, allocator: Allocator) !struct {
            distancias: []i64,
            predecessores: []?u32,
        } {
            const INF: i64 = std.math.maxInt(i64);
            const n = self.num_vertices;

            var dist = try allocator.alloc(i64, n);
            @memset(dist, INF);
            dist[origem] = 0;

            var pred = try allocator.alloc(?u32, n);
            @memset(pred, null);

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

            // Min-heap simulado com seleção simples (O(V^2))
            for (0..n) |_| {
                // Encontra vértice não visitado com menor distância
                var u: ?u32 = null;
                var min_dist: i64 = INF;
                for (0..n) |v| {
                    if (!visitado[v] and dist[v] < min_dist) {
                        min_dist = dist[v];
                        u = @intCast(v);
                    }
                }

                if (u == null) break;
                const atual = u.?;
                visitado[atual] = true;

                // Relaxa arestas
                for (self.adjacencias[atual].items) |aresta| {
                    const nova_dist = dist[atual] + aresta.peso;
                    if (nova_dist < dist[aresta.destino]) {
                        dist[aresta.destino] = nova_dist;
                        pred[aresta.destino] = atual;
                    }
                }
            }

            return .{ .distancias = dist, .predecessores = pred };
        }

        /// Reconstrói o caminho da origem até um destino.
        pub fn reconstruirCaminho(predecessores: []const ?u32, destino: u32, allocator: Allocator) ![]u32 {
            var caminho = std.ArrayList(u32).init(allocator);

            var atual: ?u32 = destino;
            while (atual) |v| {
                try caminho.append(v);
                atual = predecessores[v];
            }

            // Inverte o caminho
            var slice = try caminho.toOwnedSlice();
            std.mem.reverse(u32, slice);
            return slice;
        }

        /// Bellman-Ford — caminho mínimo (aceita pesos negativos).
        /// Retorna null se detectar ciclo negativo.
        pub fn bellmanFord(self: *const Self, origem: u32, allocator: Allocator) !?[]i64 {
            const INF: i64 = std.math.maxInt(i64);
            const n = self.num_vertices;

            var dist = try allocator.alloc(i64, n);
            @memset(dist, INF);
            dist[origem] = 0;

            // Relaxa V-1 vezes
            for (0..n - 1) |_| {
                for (0..n) |u| {
                    if (dist[u] == INF) continue;
                    for (self.adjacencias[u].items) |aresta| {
                        const nova_dist = dist[u] + aresta.peso;
                        if (nova_dist < dist[aresta.destino]) {
                            dist[aresta.destino] = nova_dist;
                        }
                    }
                }
            }

            // Verifica ciclo negativo
            for (0..n) |u| {
                if (dist[u] == INF) continue;
                for (self.adjacencias[u].items) |aresta| {
                    if (dist[u] + aresta.peso < dist[aresta.destino]) {
                        allocator.free(dist);
                        return null; // Ciclo negativo detectado!
                    }
                }
            }

            return dist;
        }
    };
}

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(false).init(allocator, 6);
    defer grafo.deinit();

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

    // Dijkstra a partir do vértice 0
    const resultado = try grafo.dijkstra(0, allocator);
    defer allocator.free(resultado.distancias);
    defer allocator.free(resultado.predecessores);

    try stdout.writeAll("=== Dijkstra (origem=0) ===\n");
    for (resultado.distancias, 0..) |dist, v| {
        if (dist == std.math.maxInt(i64)) {
            try stdout.print("  0 -> {d}: INF\n", .{v});
        } else {
            try stdout.print("  0 -> {d}: {d}\n", .{ v, dist });
        }
    }

    // Caminho mínimo para vértice 5
    const caminho = try GrafoPonderado(false).reconstruirCaminho(resultado.predecessores, 5, allocator);
    defer allocator.free(caminho);

    try stdout.writeAll("\nCaminho mais curto 0 -> 5: ");
    for (caminho, 0..) |v, i| {
        if (i > 0) try stdout.writeAll(" -> ");
        try stdout.print("{d}", .{v});
    }
    try stdout.print(" (custo: {d})\n", .{resultado.distancias[5]});

    // Bellman-Ford
    try stdout.writeAll("\n=== Bellman-Ford (origem=0) ===\n");
    if (try grafo.bellmanFord(0, allocator)) |dist_bf| {
        defer allocator.free(dist_bf);
        for (dist_bf, 0..) |dist, v| {
            try stdout.print("  0 -> {d}: {d}\n", .{ v, dist });
        }
        try stdout.writeAll("Sem ciclo negativo.\n");
    } else {
        try stdout.writeAll("  Ciclo negativo detectado!\n");
    }
}