Modify Graph Edge Weights Solution in C++

Problem Description

Ah, the classic “Modify Graph Edge Weights” problem! It’s like trying to convince your friend to pay for dinner after you’ve already ordered the most expensive dish on the menu. You’re given a graph with edges that may have negative weights (because who doesn’t love a little drama?), and your task is to adjust these weights so that the shortest path from a source to a destination meets a specific target weight.

Imagine you’re planning a road trip, and you want to take the scenic route (which is longer) but still arrive at your destination on time. You need to modify the weights of some roads (edges) to ensure your travel time (path weight) is just right. If only life were as simple as changing a few numbers!

Code Solution


class Solution {
 public:
  vector> modifiedGraphEdges(int n, vector>& edges,
                                         int source, int destination,
                                         int target) {
    constexpr int kMax = 2'000'000'000;
    vector>> graph(n);

    for (const vector& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      if (w == -1)
        continue;
      graph[u].emplace_back(v, w);
      graph[v].emplace_back(u, w);
    }

    int distToDestination = dijkstra(graph, source, destination);
    if (distToDestination < target)
      return {};
    if (distToDestination == target) {
      for (vector& edge : edges)
        if (edge[2] == -1)
          edge[2] = kMax;
      return edges;
    }

    for (int i = 0; i < edges.size(); ++i) {
      const int u = edges[i][0];
      const int v = edges[i][1];
      int& w = edges[i][2];
      if (w != -1)
        continue;
      w = 1;
      graph[u].emplace_back(v, 1);
      graph[v].emplace_back(u, 1);
      distToDestination = dijkstra(graph, source, destination);
      if (distToDestination <= target) {
        w += target - distToDestination;
        for (int j = i + 1; j < edges.size(); ++j)
          if (edges[j][2] == -1)
            edges[j][2] = kMax;
        return edges;
      }
    }

    return {};
  }

 private:
  int dijkstra(const vector>>& graph, int src, int dst) {
    vector dist(graph.size(), INT_MAX);

    dist[src] = 0;
    using P = pair;  // (d, u)
    priority_queue, greater<>> minHeap;
    minHeap.emplace(dist[src], src);

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (d > dist[u])
        continue;
      for (const auto& [v, w] : graph[u])
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.emplace(dist[v], v);
        }
    }

    return dist[dst];
  }
};

Approach Explanation

The code uses Dijkstra's algorithm to find the shortest path from the source to the destination. Initially, it builds a graph from the edges, ignoring those with a weight of -1. It then checks if the current shortest path meets the target. If not, it iteratively modifies the weights of the edges with -1, attempting to find a valid path that meets the target weight.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O((E + V) log V)
Space Complexity	O(V + E)

Real-World Example

Think of a delivery service trying to optimize routes. They have certain roads (edges) that are under construction (negative weights). The goal is to adjust the weights of these roads to ensure that the delivery time (path weight) is within a specific limit. By modifying the weights, they can ensure timely deliveries without taking unnecessary detours.