Hard
题目描述
给你一个无向加权连通图，包含 n 个标记为 0 到 n - 1 的节点，以及一个整数数组 edges，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条权重为 wi 的边。
某些边的权重为 -1（wi = -1），而其他边具有正权重（wi > 0）。
你的任务是修改所有权重为 -1 的边，为它们分配 [1, 2 * 109] 范围内的正整数值，使得节点 source 和 destination 之间的最短距离等于整数 target。如果有多种修改方式使得 source 和 destination 之间的最短距离等于 target，任何一种都被认为是正确的。
如果可能使从 source 到 destination 的最短距离等于 target，则返回包含所有边（即使是未修改的边）的数组，顺序任意；如果不可能，则返回空数组。
注意：不允许修改初始权重为正数的边的权重。
示例 1：
输入：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。
示例 2：
输入：n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
输出：[]
解释：上图包含初始边。通过修改权重为 -1 的边，无法使从 0 到 2 的距离等于 6。因此返回空数组。
示例 3：
输入：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。
约束条件：
1 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= ai, bi < nwi = -1或1 <= wi <= 107ai != bi0 <= source, destination < nsource != destination1 <= target <= 109- 图是连通的，没有自环或重复边
解题思路
这是一道复杂的图论题，需要通过修改权重为-1的边来使最短路径长度等于目标值。解题思路如下：
核心思路：
- 首先验证可行性：计算只使用正权重边的最短路径，如果已经小于target则不可能
- 将所有-1边临时设为1，计算最短路径，如果大于target则不可能
- 使用二分搜索的思想：逐步调整-1边的权重，使最短路径接近target
具体步骤：
- 先将所有-1边设为大值(如2×10⁹)，计算最短路径，验证基本连通性
- 将所有-1边设为1，计算最短路径，如果大于target则无解
- 逐个处理-1边：对每条-1边，尝试通过调整其权重使最短路径等于target
- 关键在于找到合适的边进行调整：如果存在边(u,v)使得dist[u] + dist[v] + 1 < target，则可以将该边权重设为target - dist[u] - dist[v]
算法优化：
- 使用Dijkstra算法计算最短路径
- 采用贪心策略：优先调整能够直接达到目标的边
- 其余未调整的-1边设为足够大的值避免影响最短路径
这种方法时间复杂度为O(E × (V + E)logV)，在约束条件下是可行的。
代码实现
class Solution {
public:
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
vector<vector<pair<int, int>>> graph(n);
for (int i = 0; i < edges.size(); i++) {
int u = edges[i][0], v = edges[i][1];
graph[u].push_back({v, i});
graph[v].push_back({u, i});
}
auto dijkstra = [&]() -> int {
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, idx] : graph[u]) {
int w = edges[idx][2];
if (w == -1) w = 1;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist[destination];
};
int minDist = dijkstra();
if (minDist < target) return {};
if (minDist == target) {
for (auto& edge : edges) {
if (edge[2] == -1) edge[2] = 2e9;
}
return edges;
}
for (int i = 0; i < edges.size(); i++) {
if (edges[i][2] != -1) continue;
edges[i][2] = 1;
int dist = dijkstra();
if (dist <= target) {
edges[i][2] = target - dist + 1;
for (int j = i + 1; j < edges.size(); j++) {
if (edges[j][2] == -1) edges[j][2] = 2e9;
}
return edges;
}
}
return {};
}
};
class Solution:
def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
import heapq
graph = [[] for _ in range(n)]
for i, (u, v, w) in enumerate(edges):
graph[u].append((v, i))
graph[v].append((u, i))
def dijkstra():
dist = [float('inf')] * n
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, idx in graph[u]:
w = edges[idx][2]
if w == -1:
w = 1
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist[destination]
min_dist = dijkstra()
if min_dist < target:
return []
if min_dist == target:
for edge in edges:
if edge[2] == -1:
edge[2] = 2 * 10**9
return edges
for i, edge in enumerate(edges):
if edge[2] != -1:
continue
edge[2] = 1
dist = dijkstra()
if dist <= target:
edge[2] = target - dist + 1
for j in range(i + 1, len(edges)):
if edges[j][2] == -1:
edges[j][2] = 2 * 10**9
return edges
return []
public class Solution {
public int[][] ModifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
var graph = new List<(int, int)>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<(int, int)>();
}
for (int i = 0; i < edges.Length; i++) {
int u = edges[i][0], v = edges[i][1];
graph[u].Add((v, i));
graph[v].Add((u, i));
}
int Dijkstra() {
var dist = new int[n];
Array.Fill(dist, int.MaxValue);
var pq = new PriorityQueue<int, int>();
dist[source] = 0;
pq.Enqueue(source, 0);
while (pq.Count > 0) {
int u = pq.Dequeue();
foreach (var (v, idx) in graph[u]) {
int w = edges[idx][2];
if (w == -1) w = 1;
if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.Enqueue(v, dist[v]);
}
}
}
return dist[destination];
}
int minDist = Dijkstra();
if (minDist < target) return new int[0][];
if (minDist == target) {
foreach (var edge in edges) {
if (edge[2] == -1) edge[2] = 2000000000;
}
return edges;
}
for (int i = 0; i < edges.Length; i++) {
if (edges[i][2] != -1) continue;
edges[i][2] = 1;
int dist = Dijkstra();
if (dist <= target) {
edges[i][2] = target - dist + 1;
for (int j = i + 1; j < edges.Length; j++) {
if (edges[j][2] == -1) edges[j][2] = 2000000000;
}
return edges;
}
}
return new int[0][];
}
}
var modifiedGraphEdges = function(n, edges, source, destination, target) {
const INF = 2e9;
function dijkstra(graph, src, dest) {
const dist = new Array(n).fill(INF);
const pq = [[0, src]];
dist[src] = 0;
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue;
for (const [v, w] of graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push([dist[v], v]);
}
}
}
return dist[dest];
}
function buildGraph(useModified = false) {
const graph = Array.from({length: n}, () => []);
for (let i = 0; i < edges.length; i++) {
const [u, v, w] = edges[i];
const weight = w === -1 ? (useModified ? 1 : INF) : w;
graph[u].push([v, weight]);
graph[v].push([u, weight]);
}
return graph;
}
// Check if already possible without modifying -1 edges
const graphWithoutModified = buildGraph(false);
const distWithoutModified = dijkstra(graphWithoutModified, source, destination);
if (distWithoutModified < target) {
return [];
}
// Check if possible with all -1 edges set to 1
const graphWithModified = buildGraph(true);
const distWithModified = dijkstra(graphWithModified, source, destination);
if (distWithModified > target) {
return [];
}
// Binary search approach - modify edges one by one
const result = [...edges];
for (let i = 0; i < result.length; i++) {
if (result[i][2] === -1) {
result[i][2] = 1;
}
}
// Build graph with current modifications
const graph = Array.from({length: n}, () => []);
for (const [u, v, w] of result) {
graph[u].push([v, w]);
graph[v].push([u, w]);
}
const currentDist = dijkstra(graph, source, destination);
if (currentDist === target) {
return result;
}
if (currentDist > target) {
return [];
}
// Need to increase some edge weight
const diff = target - currentDist;
for (let i = 0; i < result.length; i++) {
if (edges[i][2] === -1) {
result[i][2] = 1 + diff;
// Rebuild graph
const newGraph = Array.from({length: n}, () => []);
for (const [u, v, w] of result) {
newGraph[u].push([v, w]);
newGraph[v].push([u, w]);
}
const newDist = dijkstra(newGraph, source, destination);
if (newDist === target) {
return result;
}
if (newDist > target) {
// Binary search for the right weight
let left = 1, right = 1 + diff;
while (left < right) {
const mid = Math.floor((left + right) / 2);
result[i][2] = mid;
const testGraph = Array.from({length: n}, () => []);
for (const [u, v, w] of result) {
testGraph[u].push([v, w]);
testGraph[v].push([u, w]);
}
const testDist = dijkstra(testGraph, source, destination);
if (testDist <= target) {
left = mid + 1;
} else {
right = mid;
}
}
result[i][2] = left - 1;
const finalGraph = Array.from({length: n}, () => []);
for (const [u, v, w] of result) {
finalGraph[u].push([v, w]);
finalGraph[v].push([u, w]);
}
if (dijkstra(finalGraph, source, destination) === target) {
return result;
}
result[i][2] = left;
const finalGraph2 = Array.from({length: n}, () => []);
for (const [u, v, w] of result) {
finalGraph2[u].push([v, w]);
finalGraph2[v].push([u, w]);
}
if (dijkstra(finalGraph2, source, destination) === target) {
return result;
}
}
break;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(E × (V + E)logV)，其中E为边数，V为节点数。需要对每条-1边进行一次Dijkstra计算 |
| 空间复杂度 | O(V + E)，用于存储图的邻接表和Dijkstra算法的距离数组 |