modify-graph-edge-weights

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an undirected weighted connected 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] = [ai, bi, wi]</code> indicates that there is an edge between nodes <code>ai</code> and <code>bi</code> with weight <code>wi</code>.

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

Your task is to modify all edges with a weight of <code>-1</code> by assigning them positive integer values in the range <code>[1, 2 * 109]</code> so that the shortest distance between the nodes <code>source</code> and <code>destination</code> becomes equal to an integer <code>target</code>. If there are multiple modifications 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.

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

Note: You are not allowed to modify the weights of edges with initial positive weights.

&nbsp;
Example 1:

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

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

Example 2:

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

<pre>
Input: n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
Output: []
Explanation: 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>

Example 3:

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

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= ai, bi&nbsp;&lt;&nbsp;n</code></li>
	<li><code>wi&nbsp;= -1&nbsp;</code>or <code>1 &lt;= wi&nbsp;&lt;= 107</code></li>
	<li><code>ai&nbsp;!=&nbsp;bi</code></li>
	<li><code>0 &lt;= source, destination &lt; n</code></li>
	<li><code>source != destination</code></li>
	<li><code>1 &lt;= target &lt;= 109</code></li>
	<li>The graph is connected, and there are no self-loops or repeated edges</li>
</ul>

modifiedGraphEdges

Modify Graph Edge Weights

Graph

Shortest Path

Heap (Priority Queue)

给你一个 <code>n</code>&nbsp;个节点的 无向带权连通&nbsp;图，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，再给你一个整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [ai, bi, wi]</code>&nbsp;表示节点&nbsp;<code>ai</code> 和&nbsp;<code>bi</code>&nbsp;之间有一条边权为&nbsp;<code>wi</code>&nbsp;的边。

部分边的边权为&nbsp;<code>-1</code>（<code>wi = -1</code>），其他边的边权都为 正&nbsp;数（<code>wi &gt; 0</code>）。

你需要将所有边权为 <code>-1</code>&nbsp;的边都修改为范围&nbsp;<code>[1, 2 * 109]</code>&nbsp;中的 正整数&nbsp;，使得从节点&nbsp;<code>source</code>&nbsp;到节点&nbsp;<code>destination</code>&nbsp;的 最短距离&nbsp;为整数&nbsp;<code>target</code>&nbsp;。如果有 多种&nbsp;修改方案可以使&nbsp;<code>source</code> 和&nbsp;<code>destination</code>&nbsp;之间的最短距离等于&nbsp;<code>target</code>&nbsp;，你可以返回任意一种方案。

如果存在使 <code>source</code>&nbsp;到 <code>destination</code>&nbsp;最短距离为 <code>target</code>&nbsp;的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 空数组&nbsp;。

注意：你不能修改一开始边权为正数的边。

&nbsp;

示例 1：

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

<pre>
输入：n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
输出：[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
解释：上图展示了一个满足题意的修改方案，从 0 到 1 的最短距离为 5 。
</pre>

示例 2：

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

<pre>
输入：n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
输出：[]
解释：上图是一开始的图。没有办法通过修改边权为 -1 的边，使得 0 到 2 的最短距离等于 6 ，所以返回一个空数组。
</pre>

示例 3：

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

<pre>
输入：n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
输出：[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
解释：上图展示了一个满足题意的修改方案，从 0 到 2 的最短距离为 6 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= ai, bi&nbsp;&lt;&nbsp;n</code></li>
	<li><code>wi&nbsp;= -1</code> 或者 <code>1 &lt;= wi&nbsp;&lt;= 107</code></li>
	<li><code>ai&nbsp;!=&nbsp;bi</code></li>
	<li><code>0 &lt;= source, destination &lt; n</code></li>
	<li><code>source != destination</code></li>
	<li><code>1 &lt;= target &lt;= 109</code></li>
	<li>输入的图是连通图，且没有自环和重边。</li>
</ul>