<p>You are given an <strong>undirected weighted</strong> <strong>connected</strong> graph containing <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>, and an integer array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>, w<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with weight <code>w<sub>i</sub></code>.</p>

<p>Some edges have a weight of <code>-1</code> (<code>w<sub>i</sub> = -1</code>), while others have a <strong>positive</strong> weight (<code>w<sub>i</sub> &gt; 0</code>).</p>

<p>Your task is to modify <strong>all edges</strong> with a weight of <code>-1</code> by assigning them <strong>positive integer values </strong>in the range <code>[1, 2 * 10<sup>9</sup>]</code> so that the <strong>shortest distance</strong> between the nodes <code>source</code> and <code>destination</code> becomes equal to an integer <code>target</code>. If there are <strong>multiple</strong> <strong>modifications</strong> that make the shortest distance between <code>source</code> and <code>destination</code> equal to <code>target</code>, any of them will be considered correct.</p>

<p>Return <em>an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from </em><code>source</code><em> to </em><code>destination</code><em> equal to </em><code>target</code><em>, or an <strong>empty array</strong> if it&#39;s impossible.</em></p>

<p><strong>Note:</strong> You are not allowed to modify the weights of edges with initial positive weights.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/18/graph.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
<strong>Output:</strong> [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
<strong>Explanation:</strong> The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/18/graph-2.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
<strong>Output:</strong> []
<strong>Explanation:</strong> The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned.
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/19/graph-3.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
<strong>Output:</strong> [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
<strong>Explanation:</strong> The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code><font face="monospace">1 &lt;= edges.length &lt;= n * (n - 1) / 2</font></code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i&nbsp;</sub>&lt;&nbsp;n</code></li>
	<li><code><font face="monospace">w<sub>i</sub>&nbsp;= -1&nbsp;</font></code>or <code><font face="monospace">1 &lt;= w<sub>i&nbsp;</sub>&lt;= 10<sup><span style="font-size: 10.8333px;">7</span></sup></font></code></li>
	<li><code>a<sub>i&nbsp;</sub>!=&nbsp;b<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt; n</code></li>
	<li><code>source != destination</code></li>
	<li><code><font face="monospace">1 &lt;= target &lt;= 10<sup>9</sup></font></code></li>
	<li>The graph is connected, and there are no self-loops or repeated edges</li>
</ul>

class Solution {
public:
    
    // REMEMBER, THERE COULD BE MULTIPLE SHORTEST PATHS!!!!!!!
    // minimum path cost could be shared by:
    // 1. a fixed path
    // 2. as well as multiple adjustable paths!
    
    
    // have a few options of optimizing the code:
    // 1. tweak algo so that a new adjacency graph is not created every single time, instead,
    //    the adjacency list with the weights is simply updated
    // 2. reduce the number of binary search iterations by checking if the new shortest path
    //    less than old shortest path of fixed size, then simply cut using the
    //    division and remainder logic (since if already shortest path, making its edge weights smaller will still have it guaranteed be the shortest path!)
    
    void binarySearch(int n, int lo, int hi, vector<vector<int>>& graph, vector<int>& ind_to_adjust, vector<vector<int>>& update_ind, vector<int>& is_adjustable, int source, int destination, vector<int>& path, int target, vector<vector<int>>& edges, vector<vector<int>>& ind){

        int still_need = -1;
        
        int shortest;
        
        int mid = (lo + hi) / 2;
        while(true){
            
            updateGraph(graph, ind_to_adjust, update_ind, is_adjustable, mid);

            path.clear();
            
            int shortest_mid = shortestPath(graph, source, destination, path);
            if(shortest_mid == target){
                finalizeEdges(edges, ind_to_adjust, mid);
                return;
            }
            
            if(shortest_mid > target){
                hi = mid;
                mid = (lo + hi) / 2;
                continue;
            }
            
            for(int i = 0; i < edges.size(); ++i){
                if(is_adjustable[i] == 1) edges[i][2] = mid + 1;
            }
            updateGraph(graph, ind_to_adjust, update_ind, is_adjustable, mid + 1);
            
            // REMEMBER TO CLEAR PATH!
            path.clear();
            
            int shortest_mid_1 = shortestPath(graph, source, destination, path);
            if(shortest_mid_1 == target){
                finalizeEdges(edges, ind_to_adjust, mid + 1);
                return;
            }
            
            if(shortest_mid_1 < target){
                lo = mid + 1;
                mid = (lo + hi) / 2;
                continue;
            }
            // at this point, shortest_mid < target and target < shortest_mid_1
            
            // get the correct path
            path.clear();
            for(int i = 0; i < edges.size(); ++i){
                if(is_adjustable[i] == 1) edges[i][2] = mid;
            }
            graph = getGraph(n, edges);
            
            shortestPath(graph, source, destination, path);
            still_need = target - shortest_mid;
            
            // excess = shortest_mid_1 - target;
            // cout << "mid: " << mid << endl;
            break;
        }

        while(still_need > 0){
            
            vector<int> to_adjust (edges.size(), 0);
            int num_adjustable = 0;

            // cout << "path.size() " << path.size() << endl;

            for(int i = 0; i < (int)path.size() - 1; ++i){
                int u = path[i];
                int v = path[i + 1];
                int idx = ind[u][v];
                if(is_adjustable[idx] == 1){
                    num_adjustable++;
                    to_adjust[idx] = 1;
                }
            }

//             cout << "num_adjustable " << num_adjustable << endl;
//             cout << "is_adjustable" << endl;
//             for(int x : is_adjustable) cout << x;
//             cout << endl;
//             cout << "to_adjust" << endl;
//             for(int x : to_adjust) cout << x;
//             cout << endl;

//             cout << "still_need: " << still_need << endl;

            for(int i = 0; i < to_adjust.size(); ++i){
                if(to_adjust[i] == 1){
                    if(still_need > 0){
                        edges[i][2]++;
                        still_need--;
                    }
                }
            }

            path.clear();
            graph = getGraph(n, edges);
            shortest = shortestPath(graph, source, destination, path);
            // cout << "new shortest: " << shortest << endl;

            still_need = target - shortest;
        }
        return;
    }
    
    void finalizeEdges(vector<vector<int>>& edges, vector<int>& ind_to_adjust, int w){
        for(int i : ind_to_adjust){
            edges[i][2] = w;
        }
    }
    void updateGraph(vector<vector<int>>& graph, vector<int>& ind_to_adjust, vector<vector<int>>& update_ind, vector<int>& is_adjustable, int w){
        
         for(int i : ind_to_adjust){
            int a = update_ind[i][0];
            int b = update_ind[i][1];
            graph[a][b] = w;
            a = update_ind[i][2];
            b = update_ind[i][3];
            graph[a][b] = w;
        }
    }
    
    vector<vector<int>> solve(int n, vector<vector<int>>& edges, vector<int>& is_adjustable, vector<vector<int>>& ind, int source, int destination, int target, vector<int>& path, int fixed_best){
                    
        vector<vector<int>> shadow_graph (n);
        vector<vector<int>> update_ind (edges.size()); // stores idx of weights to allow
        // for quick updates of graph
        for(int i = 0; i < edges.size(); ++i){
            int u = edges[i][0];
            int v = edges[i][1];
            int w = edges[i][2];
            int len_u = shadow_graph[u].size();
            int len_v = shadow_graph[v].size();
            update_ind[i] = {u, len_u + 1, v, len_v + 1}; // {i, j, i, j}
            
            shadow_graph[u].push_back(v);
            shadow_graph[u].push_back(w);
            shadow_graph[v].push_back(u);
            shadow_graph[v].push_back(w);
        }
        
        vector<int> ind_to_adjust;
        for(int i = 0; i < is_adjustable.size(); ++i){
            if(is_adjustable[i] == 1) ind_to_adjust.push_back(i);
        }
        
        // replace all adjustable edges with minimum weight, 1
        for(int i = 0; i < edges.size(); ++i){
            if(is_adjustable[i] == 1) edges[i][2] = 1;
        }
        vector<vector<int>> graph = getGraph(n, edges);        
        
        
        int shortest = shortestPath(graph, source, destination, path);
        
        // cout << "shortest " << shortest << endl;
        
        if(shortest > target) return {};
        if(shortest == target) return edges;
        
        
        // int excess = -1;
        int still_need = -1;
        
        // binary search
        int lo = -1;
        int hi = -1;
        updateGraph(graph, ind_to_adjust, update_ind, is_adjustable, 100);
        path.clear();
        shortest = shortestPath(graph, source, destination, path);
        if(shortest == target){
            finalizeEdges(edges, ind_to_adjust, 100);
            return edges;
        }
        if(shortest > target){
            lo = 0;
            hi = 100;
            binarySearch(n, lo, hi, graph, ind_to_adjust, update_ind, is_adjustable, source, destination, path, target, edges, ind);
            return edges;
        }
        updateGraph(graph, ind_to_adjust, update_ind, is_adjustable, 10000000);
        path.clear();
        shortest = shortestPath(graph, source, destination, path);
        if(shortest == target){
            finalizeEdges(edges, ind_to_adjust, 10000000);
            return edges;
        }
        if(shortest > target){
            lo = 0;
            hi = 10000000;
            binarySearch(n, lo, hi, graph, ind_to_adjust, update_ind, is_adjustable, source, destination, path, target, edges, ind);
            return edges;
        }
        lo = 0;
        hi = 1000000001;
        binarySearch(n, lo, hi, graph, ind_to_adjust, update_ind, is_adjustable, source, destination, path, target, edges, ind);
        return edges;
    }
    
    void processEdges(vector<vector<int>>& edges, vector<vector<int>>& adjustable, vector<vector<int>>& unadjustable, vector<int>& is_adjustable){
        for(int i = 0; i < edges.size(); ++i){
            vector<int>& edge = edges[i];
            int w = edge[2];
            if(w == -1){
                adjustable.push_back(edge);
                is_adjustable[i] = 1;
            }
            else unadjustable.push_back(edge);
        }
    }
    vector<vector<int>> getGraph(int n, vector<vector<int>>& edges){
        vector<vector<int>> graph (n);
        for(vector<int>& edge : edges){
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph[u].push_back(v);
            graph[u].push_back(w);
            graph[v].push_back(u);
            graph[v].push_back(w);
        }
        return graph;
    }
    int shortestPath(vector<vector<int>>& graph, int source, int destination, vector<int>& path){
        // return -1 means no path exists
        if(graph[source].size() == 0) return -1;
        if(graph[destination].size() == 0) return -1;
        
        vector<long long> best (graph.size(), INT_MAX);
        priority_queue<vector<long long>, vector<vector<long long>>, greater<vector<long long>>> pq;
        pq.push( {0, source, -1} ); // {dis, node, prev}
        vector<int> searched (graph.size(), 0);
        vector<int> prev (graph.size(), -1);
        while(pq.size() > 0){
            int d = pq.top()[0];
            int node = pq.top()[1];
            int prev_node = pq.top()[2];
            pq.pop();
            
            if(searched[node] == 1) continue;
            
            searched[node] = 1;
            best[node] = d;
            prev[node] = prev_node;
            
            if(node == destination) break;
            
            for(int idx = 0; idx < graph[node].size(); idx += 2){
                int adj = graph[node][idx];
                long long w = graph[node][idx + 1];
                // long long tmp = graph[node][idx + 1];
                // if(tmp + d > INT_MAX) continue;
                if(d + w < best[adj]){
                    pq.push( {d + w, adj, node} );
                }
            }
        }
        if(best[destination] != INT_MAX){
            int node = destination;
            path.push_back(destination);
            while(node != source){
                node = prev[node];
                path.push_back(node);
            }
            return best[destination];
        }
        return -1;
    }
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
        
        
        
        // make it so that you don't have to make a new graph every single time you update
        // the edges, all you do is update the weights of the edges in the graph, rather
        // that recreating the adjacency list in the graph!
        
        
        
        // 1 2 4 8 16 32 16 8 4 2 1
        // 0 1 2 3 4  5  4  3 2 1 0
        // 2 ^ 25
        // impossible for an existing path to have an edge weight of 10^9, maximum path
        // weight would be 99 * 10^7, or 990 million
        // if there is already an existing path with weight less than target, then
        // impossible, since cannot modify edges with weights already assigned
        // if there is already an existing path with weight equal to target, then assign
        // -1 edges with max weight, 2 * 10^9
        // if there is already an existing path with weight greater than target, then assign
        // all -1 edges with min weight, 1, then if shortest path still greater than target, impossible, but if shortest path less than target, then possible, we incrementally adjust the edge weights until the shortest path is exactly equal to target (maybe we could use a binary search, but remember, the edge weights must be integral). Keep track of the nodes in shortest path using Dijkstra's, remember the previous node, so that when we retrace the path we can collect the adjustable edge weights, and adjust them to make up for the difference of (target - shortest_path) by dividing weights evenly (some possibly have remainder)
        
        // if there is no existing path between node and target, then do same as above: start by assigning all -1s with 1s, then find shortest path again. If greater than target, impossible. If equal to target, possible. If less than target, increment the edge weights until equal to target
        vector<int> is_adjustable (edges.size(), 0); // is edge adjustable
        vector<vector<int>> adjustable; // adjustable and unadjustable edges
        vector<vector<int>> unadjustable;
        processEdges(edges, adjustable, unadjustable, is_adjustable);
        vector<vector<int>> unadjustable_graph = getGraph(n, unadjustable);
        vector<vector<int>> matrix_adjustable (n, vector<int> (n, 0));
        vector<vector<int>> ind (n, vector<int> (n, -1));
        for(int i = 0; i < edges.size(); ++i){
            vector<int>& edge = edges[i];
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            ind[u][v] = i;
            ind[v][u] = i;
            if(w == -1){
                matrix_adjustable[u][v] = 1;
                matrix_adjustable[v][u] = 1;
            }
        }
        
        
        int fixed_best = INT_MAX;
        
        vector<int> path;
        int shortest = shortestPath(unadjustable_graph, source, destination, path);
        
        if(shortest == -1){ // all paths must go through an adjustable edge
            
            // cout << "check2" << endl;
            return solve(n, edges, is_adjustable, ind, source, destination, target, path, fixed_best);
            
        }
        else{ // fixed shortest path exists;
            
            // cout << "check3" << endl;
            
            if(shortest < target) return {};
            if(shortest == target){
                // set all adjustable edges to INT_MAX
                for(int i = 0; i < edges.size(); ++i){
                    if(edges[i][2] == -1) edges[i][2] = 2000000000;
                }
                return edges;
            }
            
            // shortest > target
            path.clear();
            
            fixed_best = shortest;
            
            return solve(n, edges, is_adjustable, ind, source, destination, target, path, fixed_best);
        }
        return edges;
    }
};
490887