Leetcode Problem 2699. Modify Graph Edge Weights

2699. Modify Graph Edge Weights

Leetcode Solutions

Binary search + SPFA

  1. Initialize a list to store the indices of edges with a weight of -1.
  2. Perform a binary search on the number of -1 weighted edges to assign them a weight of 1.
  3. For each binary search iteration: a. Construct a graph with the current number of -1 weighted edges set to 1. b. Run SPFA from the source and store distances in d1. c. If the distance to the destination equals the target, finalize the edge weights and return the result. d. If the distance is less than the target, run SPFA from the destination and store distances in d2. e. Check if setting any of the remaining -1 weighted edges can make the distance equal to the target.
  4. If no configuration is found, return an empty array.
UML Thumbnail

Dijkstra's Algorithm with Edge Weight Adjustment

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...