Another BFS

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.graphs;

import java.util.*;

/* * ============================================================================================ * PROBLEM: Another BFS (Shortest Path with Weights 1 and 2) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a weighted undirected graph with A nodes, a source C, and destination D. * All edge weights are either 1 or 2. Find the shortest distance from C to D * in O(A + M) time. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Standard Dijkstra's Algorithm takes O(M log A). To achieve O(A + M), we must * use a standard BFS. However, BFS only works for unweighted graphs (weight = 1). * * Step 1: Graph Transformation (Edge Splitting) * We can treat an edge of weight 2 as two edges of weight 1 by introducing a * "dummy" node. * - For an edge (u, v) with weight 1: Keep it as is. * - For an edge (u, v) with weight 2: * Create a dummy node 'w'. * Add edges (u, w) and (w, v), both with weight 1. * * Step 2: BFS Execution * 1. Total nodes in transformed graph = A + (Number of weight-2 edges). * 2. Perform a standard BFS starting from node C. * 3. The distance to node D in this unweighted transformed graph will be * the shortest path distance. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A, M <= 10^5 * Weight ∈ {1, 2} * * Time Complexity: * O(A + M) - Building the transformed graph takes O(M). BFS takes O(V' + E'), * where V' <= A + M and E' <= 2M. * * Space Complexity: * O(A + M) - To store the adjacency list of the transformed graph. * ============================================================================================ / public class AnotherBFS { public int solve(int A) { // TODO: Implement solution return 0; }

public int solve(int i, int[][] b4, int i1, int i2) {
    return 1;
}

}