<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>

/*
     5
  ____________
 / -1   -1    \
(0)---(1)----(2)
 \     |
 2\    |-1
   \   |
    (3)

          10
       _________
   6  / 2    -1 \
(3)--(2)--(0)--(1)
 \_________/
     -1

          -1
       _________
  -1  / 2     6 \
(3)--(2)--(0)--(1)
 \_________/
     -1
*/
struct Edge {
    int index;
    int from;
    int to;
    int cost;
    bool isFlexible;

    Edge(int index, vector<int> edge, int flexibleCost) {
        this->index = index;
        from = edge[0];
        to = edge[1];
        cost = edge[2] == -1 ? flexibleCost : edge[2];
        isFlexible = edge[2] == -1;
    }

    Edge reverted() {
        Edge edge = *this;
        swap(edge.to, edge.from);
        return edge;
    }

    bool operator==(Edge &other) {
        return from == other.from && to == other.to && cost == other.cost && isFlexible == other.isFlexible;
    }
};

static Edge INVALID_EDGE = Edge(-1, { -1 ,-1, -1, false }, -1);

struct Vertex {
    int index;
    long long distance;
};

struct ShortestPath {
    long long distance;
    vector<Edge> edges;
    vector<Edge> flexibleEdges;
};

static const int MAX_EDGE_COST = 2000000000;

class Solution {
public:
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
        buildEdges(edges, MAX_EDGE_COST);
        buildAdjacencyMap();
        auto shortestPath = findShortestPath(source, destination, n);
        if (shortestPath.distance < target && shortestPath.flexibleEdges.size() == 0) {
            return {};
        }

        buildEdges(edges, 1);
        buildAdjacencyMap();
        shortestPath = findShortestPath(source, destination, n);

        if (shortestPath.distance > target) {
            return {};
        }
        if (shortestPath.distance < target && shortestPath.flexibleEdges.size() == 0) {
            return {};
        }

        int index = 0;
        while (index < shortestPath.flexibleEdges.size()) {
            auto flexibleEdge = shortestPath.flexibleEdges[index];
            auto edgeCost = this->edges[flexibleEdge.index].cost;
            this->edges[flexibleEdge.index].cost = MAX_EDGE_COST;

            auto nextShortestPath = findShortestPath(source, destination, n);
            if (nextShortestPath.distance < target) {
                shortestPath = nextShortestPath;
            } else {
                this->edges[flexibleEdge.index].cost = edgeCost;
                index++;
            }
        }

        auto diff = target - shortestPath.distance;
        if (!shortestPath.flexibleEdges.empty()) {
            shortestPath.flexibleEdges.front().cost += static_cast<int>(diff);
            this->edges[shortestPath.flexibleEdges.front().index].cost += static_cast<int>(diff);
        }

        vector<vector<int>> result;
        for (auto &edge : this->edges) {
            result.push_back({ edge.from, edge.to, edge.cost });
        }

        return result;
    }

    ShortestPath findShortestPath(int from, int to, int count) {
        vector<long long> distances = vector(count, LONG_LONG_MAX);
        distances[from] = 0;
        
        vector<Edge> pathEdges = vector(count, INVALID_EDGE);
        vector<Edge> flexibleEdges;

        auto comparator = [](Vertex &a, Vertex&b) { return a.distance > b.distance; };
        priority_queue<Vertex, vector<Vertex>, decltype(comparator)> queue(comparator);
        queue.push({ from, 0 });

        while (!queue.empty()) {
            auto vertex = queue.top();
            queue.pop();

            for (auto &edge : adjacencyMap[vertex.index]) {
                long long distance = vertex.distance + edges[edge.index].cost;
                if (distance < distances[edge.to]) {
                    distances[edge.to] = distance;
                    pathEdges[edge.to] = edge;
                    queue.push({ edge.to, distance });
                }
            }
        }

        ShortestPath shortestPath;
        shortestPath.distance = distances[to];

        int vertex = to;
        while (vertex != from) {
            auto edge = pathEdges[vertex];
            if (edge == INVALID_EDGE) {
                break;
            }
            shortestPath.edges.push_back(edge);
            vertex = edge.from;
            if (edge.isFlexible) {
                shortestPath.flexibleEdges.push_back(edge);
            }
        }
        reverse(shortestPath.edges.begin(), shortestPath.edges.end());

        return shortestPath;
    }

    void buildEdges(vector<vector<int>>& rawEdges, int flexibleCost) {
        edges.clear();

        for (int i = 0; i < rawEdges.size(); i++) {
            auto &rawEdge = rawEdges[i];
            Edge edge(i, rawEdge, flexibleCost);
            edges.push_back(edge);
        }
    }

    void buildAdjacencyMap() {
        adjacencyMap.clear();
        for (auto &edge : edges) {
            adjacencyMap[edge.from].push_back(edge);
            adjacencyMap[edge.to].push_back(edge.reverted());
        }
    }

private:
    vector<Edge> edges;
    unordered_map<int, vector<Edge>> adjacencyMap;
};

461467