In yesterday's LeetCode Weekly Contest 346, nearly no contestant solved the 4th problem successfully. Here is the problem, Modify Graph Edge Weights:

Given an undirected, weighted, connected graph with n nodes ($$$1 <= n <= 100$$$) and m edges ($$$1 <= m <= \frac{n(n + 1)}{2}$$$). All edges have weight in $$$[1, 10^{7}]$$$, but some have weight $$$-1$$$, denoting that you are to assign that edge some positive weight in $$$[1, 2 * 10^{9}]$$$.

Now, you are also given two nodes source and destination, as well as a positive integer target ($$$1 <= target <= 10^{9}$$$). Find ANY assignment of edge weights that make the shortest distance from source to destination exactly target, or report that there is no such assignment.

My own idea:

• Firstly, if the shortest distance from source to destination is less than target without considering any customizable edges (edges with weight $$$-1$$$), then the shortest distance will always be less than target, so it's impossible.
• Then, set all the customizable edge weights to $$$1$$$, the smallest possible. If the shortest distance from source to destination is greater than target, or if there is no path between them, then it's also impossible to make the shortest distance equal to target.
• Otherwise, I think a valid assignment of edges weights should always exist. However, I haven't thought of a way to assign the edge weights to that the shortest distance always becomes exactly target; greedy algorithms, such as making all the customizable edge weights 1 except for a single edge sometimes results in some other even-shorter path to exist, breaking the solution.

Could someone point me in the right direction?

Note that community-written solutions can be found here. The top-voted one seems promising, but one of the comments on it (from redsmolder) claims a counterexample to the greedy solution given, and further claims that Dijkstra's algorithm is "unfit" for the problem (and that Floyd-Warshall is necessary).

Thank you all!