修改圖邊權重

2699。修改圖邊權重

難度：難

主題：圖、堆（優先權隊列）、最短路徑

給你一個無向加權連通圖，其中包含標記為0到n - 1的n個節點，以及一個整數數組edges，其中edges[i] = [a_i , b _i, w_i] 表示節點a_i 和b_i 之間有一條邊，權重為w _i.

某些邊的權重為-1 (w_i = -1)，而其他邊的權重為正 (w_i > 0) .

你的任務是修改所有邊的權重為-1，方法是在[1, 2 * 109範圍內分配^正整數值 ] 使得節點來源與目的地之間的最短距離變成等於整數目標。如果有多次修改使來源和目的地之間的最短距離等於目標，則其中任何一個都將被視為正確。

如果可以使從來源到目的地的最短距離等於目標，則傳回以任意順序包含所有邊（甚至未修改的邊）的數組，如果不可能，則傳回空數組 .

注意：不允許修改初始為正權重的邊的權重。

範例1：

• 輸入： n = 5，邊= [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1] ]，來源= 0，目的地= 1，目標= 5
• 輸出： [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
• 解釋：上圖顯示了對邊緣的可能修改，使得從 0 到 1 的距離等於 5。

範例2：

• 輸入： n = 3，邊 = [[0,1,-1],[0,2,5]]，來源 = 0，目的地 = 2，目標 = 6
• 輸出： []
• 解釋： 上圖包含初始邊。透過修改權重-1的邊是不可能使從0到2的距離等於6的。因此，傳回一個空數組。

範例 3：

• 輸入： n = 4，邊= [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]]，源= 0，目的地= 2，目標= 6
• 輸出： [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
• 說明：上圖顯示了修改後的圖，其中從 0 到 2 的最短距離為 6。

約束：

• 1
• 1
• 邊[i].length == 3
• 0 i, b_i
• w_i = -1 或 1 i 7
• a_i != b_i
• 0
• 來源！ =目的地
• 1 9
• 圖是連通的，不存在自環或重複邊

提示：

1. 首先，檢查是否確實可以使從來源到目的地的最短路徑等於目標。
2. 如果從來源到目的地且沒有要修改的邊的最短路徑小於目標，則這是不可能的。
3. 如果從來源到目的地的最短路徑（包括要修改的邊並為其分配臨時權重 1）大於目標，那麼它也是不可能的。
4. 假設我們可以找到一條可修改的邊(u, v)，使得從來源到u 的最短路徑長度(dis1) 加上從v 到目的地的最短路徑長度(dis2) 小於目標(dis1) + dis2
5. 對於所有其他仍具有權重「-1」的邊，將權重更改為足夠大的數字（目標、目標 + 1 或 200000000 等）。

解：

我們可以將方法分解如下：

方法：

1. 對現有權重進行初步檢查：

   • 首先，我們只使用權重為正的邊計算從來源到目的地的最短路徑，忽略權重為 -1 的邊。
   • 如果這個距離已經大於目標，那麼就不可能修改-1邊來達到目標，所以我們回傳一個空數組。

2. 暫時分配權重 1：

   • 接下來，為所有權重為-1的邊分配臨時權重1，並重新計算最短路徑。
   • 如果這個最短路徑仍然大於目標，那麼就不可能達到目標，所以我們回傳一個空數組。

3. 修改特定邊權重：

   • 迭代權重為-1的邊緣並識別可以調整以完全匹配目標距離的邊緣。這是透過調整邊緣的權重來完成的，這樣往返於該邊緣的路徑的組合距離就可以得出準確的目標距離。
   • 對於任何剩餘的 -1 邊，分配足夠大的權重（例如 2 * 10^9）以確保它們不會影響最短路徑。

4. 回傳修改後的邊：

   • 最後，回傳修改後的邊列表。

讓我們用 PHP 實作這個解：2699。修改圖邊權重

<?php
private $kMax = 2000000000;

 /**
  * @param $n
  * @param $edges
  * @param $source
  * @param $destination
  * @param $target
  * @return array|mixed
  */
 function modifiedGraphEdges($n, $edges, $source, $destination, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
 }

 /**
  * @param $graph
  * @param $src
  * @param $dst
  * @return int|mixed
  */
 function dijkstra($graph, $src, $dst) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
 }


// Example usage:

// Example 1
$n = 5;
$edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]];
$source = 0;
$destination = 1;
$target = 5;
print_r(modifyGraphEdgeWeights($n, $edges, $source, $destination, $target)); // Output: [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]

// Example 2
$n = 3;
$edges = [[0,1,-1],[0,2,5]];
$source = 0;
$destination = 2;
$target = 6;
print_r(modifyGraphEdgeWeights($n, $edges, $source, $destination, $target)); // Output: []

// Example 3
$n = 4;
$edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]];
$source = 0;
$destination = 2;
$target = 6;
print_r(modifyGraphEdgeWeights($n, $edges, $source, $destination, $target));  // Output: [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
?>

解釋：

• dijkstra 函數計算從來源到所有其他節點的最短路徑。
• 我們最初計算忽略 -1 條邊的最短路徑。
• 如果沒有-1邊的路徑小於目標，函數會傳回一個空數組，表示無法調整權重以滿足目標。
• 否則，我們暫時將所有 -1 邊設為 1，並檢查最短路徑是否超過目標。
• 如果是，則再次無法到達目標，我們傳回一個空數組。
• 然後我們策略性地修改-1邊的權重，以實現精確目標的最短路徑。

這種方法可以有效地檢查和調整邊緣權重，確保盡可能滿足目標距離。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是修改圖邊權重的詳細內容。更多資訊請關注PHP中文網其他相關文章！