<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:
    using i64 = int64_t;
    const i64 inf = 2e9; 

    /*
        If the shortest path after deleting all modified edges is smaller than `target`,
        then it is impossible, since this is an upper bound.
        
        If the shortest path after settings all modified edges to 1 is larger than `target`,
        then it is also impossible, since this is a lower bound.

        Otherwise, it is always possible.

        To see why, consider setting all modified edges to have weight _at least_ 1. We will
        assign these edges to specific values as the algorithm handles each path. If we find the
        shortest path, then it is either less than `target` or equal to `target` since we
        eliminated the cases above. If it is equal to `target` then we are done. If it is
        less than target then there must be some unassigned edge as argued above. We can
        set this edge to be so that its distance is equal to `target`. Notice that this does
        not create an assigned path that is lower than `target` since it increases every path
        that passes through the edge. Keep doing this unitl there are no more paths with distance
        less than `target`.
    */

    using AdjList = vector<vector<int>>;
    using Weights = vector<vector<int>>;
    vector<int> shortestPath(int n, AdjList& adj, Weights& weight, int source, int destination) {
        vector<i64> dist(n, inf);
        vector<int> prev(n, -1);

        using key = pair<i64, int>;
        priority_queue<key, vector<key>, greater<key>> Q;
        
        Q.emplace(0, source);
        dist[source] = 0;

        while (!Q.empty()) {
            const auto [d, u] = Q.top();
            Q.pop();

            // ignore old value
            if (d != dist[u])
                continue;

            for (int v : adj[u]) {
                // treat unassigned edges as 1
                int w = weight[u][v] == -1 ? 1 : weight[u][v];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    prev[v] = u;
                    Q.emplace(dist[v], v);
                }
            }
        }

        vector<int> path;
        int u = destination;
        while (u != -1) {
            path.push_back(u);
            u = prev[u];
        }

        return path; 
    }

    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
        AdjList adj(n);
        Weights weight(n, vector<int>(n, inf));

        for (const auto &e : edges) {
            int u = e[0], v = e[1], w = e[2];
            adj[u].push_back(v);
            adj[v].push_back(u);
            weight[u][v] = weight[v][u] = w;
        }

        for (;;) {
            vector<int> path = shortestPath(n, adj, weight, source, destination);

            // this could be valid if source == destination, but ignore for this problem
            if (path.empty())
                assert(false);

            i64 dist = 0;
            int m = -1;
            for (int i = 1; i < path.size(); i++) {
                int u = path[i-1], v = path[i];
                dist += weight[u][v] == -1 ? 1 : weight[u][v];
                if (weight[u][v] == -1)
                    m = i;
            }

            // done
            if (m == -1) {
                if (dist != target)
                    return {};
                break;
            }

            // assign the edge
            int u = path[m-1], v = path[m];
            i64 w = target - dist + 1;
            if (w < 1)
                return {};
            weight[u][v] = weight[v][u] = w;
        }

        for (auto &e : edges) {
            int u = e[0], v = e[1];
            e[2] = weight[u][v] == -1 ? 1 : weight[u][v];
        }

        return edges;
    }
};
432047