/**
 * Floyd-Warshall: all-pairs shortest paths
 *
 * @param {number} n       - number of vertices (0-indexed: 0..n-1)
 * @param {number[][]} edges - [from, to, weight]
 * @returns {{ dist: number[][], next: (number|null)[][] }}
 *   dist[i][j] = shortest distance from i to j (Infinity if unreachable)
 *   next[i][j] = first step on the shortest path from i to j (for reconstruction)
 */
function floydWarshall(n, edges) {
  const INF = Infinity;

  // 1. Initialize distance matrix
  const dist = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  // 2. Initialize "next" matrix for path reconstruction
  //    next[i][j] = the vertex after i on the shortest path to j
  const next = Array.from({ length: n }, () => Array(n).fill(null));

  // 3. Populate direct edges
  for (const [u, v, w] of edges) {
    if (w < dist[u][v]) {        // handle parallel edges (keep smallest)
      dist[u][v] = w;
      next[u][v] = v;
    }
  }

  // Self-loops: we go "nowhere" on a zero-length path
  for (let i = 0; i < n; i++) next[i][i] = i;

  // 4. Main triple loop — the heart of Floyd-Warshall
  for (let k = 0; k < n; k++) {        // intermediate vertex
    for (let i = 0; i < n; i++) {      // source
      for (let j = 0; j < n; j++) {    // destination
        if (dist[i][k] === INF || dist[k][j] === INF) continue; // avoid Inf + Inf
        const through = dist[i][k] + dist[k][j];
        if (through < dist[i][j]) {
          dist[i][j] = through;
          next[i][j] = next[i][k];     // go to k first, then on to j
        }
      }
    }
  }

  return { dist, next };
}

// --- Path Reconstruction ---
function getPath(next, u, v) {
  if (next[u][v] === null) return [];  // unreachable
  const path = [u];
  while (u !== v) {
    u = next[u][v];
    path.push(u);
  }
  return path;
}

// --- Example usage ---
const n = 4;
const edges = [
  [0, 1, 5],
  [0, 2, 1],
  [0, 3, 3],
  [1, 3, 2],
  [2, 3, 4],
];

const { dist, next } = floydWarshall(n, edges);

console.log("Shortest distances:");
for (let i = 0; i < n; i++) {
  console.log(`  From ${i}:`, dist[i].map(d => d === Infinity ? "∞" : d));
}

console.log("\nPath from 0 to 3:", getPath(next, 0, 3)); // [0, 3]
console.log("Path from 2 to 1:", getPath(next, 2, 1)); // [] (unreachable in directed graph)

function hasNegativeCycle(dist, n) {
  for (let i = 0; i < n; i++) {
    if (dist[i][i] < 0) return true;
  }
  return false;
}

// Any path through a vertex v in a negative cycle is also -∞
function isDistInfinitelyNegative(dist, n, u, v) {
  for (let k = 0; k < n; k++) {
    // If k is in a negative cycle AND is reachable from u AND can reach v
    if (dist[k][k] < 0 && dist[u][k] !== Infinity && dist[k][v] !== Infinity) {
      return true;
    }
  }
  return false;
}

// Graph with negative cycle: 0→1 (1), 1→2 (-3), 2→1 (1)
// Cycle 1→2→1 has total weight -3+1 = -2 (negative!)
const edgesWithNegCycle = [
  [0, 1, 1],
  [1, 2, -3],
  [2, 1, 1],   // forms cycle 1→2→1 with weight -3+1 = -2
];

const { dist: d2 } = floydWarshall(3, edgesWithNegCycle);
console.log("Negative cycle?", hasNegativeCycle(d2, 3)); // true
console.log("dist[1][1] =", d2[1][1]); // < 0

/**
 * Compute transitive closure: reach[i][j] = true if j is reachable from i
 */
function transitiveClosure(n, edges) {
  // Initialize: reach[i][j] = true if direct edge i→j exists, or i === j
  const reach = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => i === j)
  );

  for (const [u, v] of edges) {
    reach[u][v] = true;
  }

  // Floyd-Warshall variant: use OR instead of min
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
      }
    }
  }

  return reach;
}

const edges = [[0, 1], [1, 2], [2, 3]];
const reach = transitiveClosure(4, edges);

console.log("0 can reach 3?", reach[0][3]); // true  (0→1→2→3)
console.log("3 can reach 0?", reach[3][0]); // false (no back edges)
console.log("2 can reach 1?", reach[2][1]); // false

/**
 * LeetCode 1334 — Find the City With the Smallest Number of Neighbors
 * at a Threshold Distance
 *
 * @param {number} n
 * @param {number[][]} edges  - [from, to, weight]
 * @param {number} distanceThreshold
 * @return {number}
 */
var findTheCity = function(n, edges, distanceThreshold) {
  const INF = Infinity;

  // 1. Initialize distance matrix
  const dist = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  // 2. Fill direct edges (undirected)
  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(dist[u][v], w);
    dist[v][u] = Math.min(dist[v][u], w); // undirected
  }

  // 3. Floyd-Warshall
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== INF && dist[k][j] !== INF) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // 4. For each city, count how many other cities are within threshold
  let bestCity = -1;
  let bestCount = Infinity;

  for (let i = 0; i < n; i++) {
    let count = 0;
    for (let j = 0; j < n; j++) {
      if (i !== j && dist[i][j] <= distanceThreshold) {
        count++;
      }
    }
    // Keep city with fewest neighbors; on tie, prefer higher index
    if (count <= bestCount) {
      bestCount = count;
      bestCity = i;
    }
  }

  return bestCity;
};

// Example: n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold=4
// Expected: 3
console.log(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)); // 3

/**
 * Network Delay Time — answered for ANY source using Floyd-Warshall
 *
 * @param {number[][]} times - [u, v, w]: directed edge u→v with delay w
 * @param {number} n         - number of nodes (1-indexed)
 * @param {number} k         - source node
 * @return {number}          - time for signal to reach all nodes, or -1
 */
var networkDelayTime = function(times, n, k) {
  const INF = Infinity;

  // Convert 1-indexed to 0-indexed
  const dist = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  for (const [u, v, w] of times) {
    dist[u - 1][v - 1] = Math.min(dist[u - 1][v - 1], w);
  }

  // Floyd-Warshall
  for (let mid = 0; mid < n; mid++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][mid] !== INF && dist[mid][j] !== INF) {
          dist[i][j] = Math.min(dist[i][j], dist[i][mid] + dist[mid][j]);
        }
      }
    }
  }

  // Answer for source k (0-indexed: k-1)
  const src = k - 1;
  let maxDelay = 0;
  for (let j = 0; j < n; j++) {
    if (dist[src][j] === INF) return -1; // node j unreachable
    maxDelay = Math.max(maxDelay, dist[src][j]);
  }
  return maxDelay;

  // Bonus: now dist[i] holds delays from ANY source i — O(1) queries!
};

console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)); // 2
console.log(networkDelayTime([[1,2,1]], 2, 1));                  // 1
console.log(networkDelayTime([[1,2,1]], 2, 2));                  // -1 (node 1 unreachable from 2)

/**
 * Transitive Closure — return a boolean matrix
 * reach[i][j] = true means vertex j is reachable from vertex i
 */
function buildTransitiveClosure(n, edges) {
  const reach = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => i === j)
  );

  for (const [u, v] of edges) {
    reach[u][v] = true;
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (reach[i][k] && reach[k][j]) {
          reach[i][j] = true;
        }
      }
    }
  }

  return reach;
}

// Example: 4 nodes, edges form 0→1→2→3 (chain)
const edges = [[0,1],[1,2],[2,3]];
const reach = buildTransitiveClosure(4, edges);

console.log("Reachability matrix:");
reach.forEach((row, i) =>
  console.log(`  ${i}:`, row.map(b => b ? "T" : "F").join(" "))
);
// 0: T T T T   (0 can reach everything)
// 1: F T T T   (1 can reach 1,2,3)
// 2: F F T T   (2 can reach 2,3)
// 3: F F F T   (3 can only reach itself)

/**
 * Return all vertices that lie on a negative cycle.
 */
function findNegativeCycleVertices(n, edges) {
  const INF = Infinity;
  const dist = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(dist[u][v], w);
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== INF && dist[k][j] !== INF) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // Vertices with dist[v][v] < 0 are on a negative cycle
  const onNegCycle = [];
  for (let v = 0; v < n; v++) {
    if (dist[v][v] < 0) onNegCycle.push(v);
  }
  return onNegCycle;
}

// Graph: 0→1 (2), 1→2 (-5), 2→0 (1)
// Cycle 0→1→2→0 has weight 2 + (-5) + 1 = -2 (negative!)
const edgesNeg = [[0,1,2],[1,2,-5],[2,0,1]];
console.log("Vertices on negative cycle:", findNegativeCycleVertices(3, edgesNeg));
// [0, 1, 2] — all three are part of the cycle

// Graph with no negative cycle
const edgesPos = [[0,1,3],[1,2,1],[2,0,5]];
console.log("Vertices on negative cycle:", findNegativeCycleVertices(3, edgesPos));
// [] — cycle weight = 3+1+5 = 9 (positive)