Modify Graph Edge Weights
Problem
An undirected graph has n nodes and edges [u, v, w]. Edges with w = -1 are erased and must be re-assigned any positive integer in [1, 2·10⁹]. Edges with a positive weight are fixed. Assign weights to the erased edges so the shortest path from source to destination equals target exactly, or report that it is impossible.
First fix every -1 edge to 1 and check the shortest distance is not already above target. Then, processing erased edges one at a time, raise each so the current shortest path through it hits the target, re-running Dijkstra after each change.
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,4],[0,3,3],[4,3,1]]import heapq
def modify_graph_edges(n, edges, source, destination, target):
INF = float('inf')
def dijkstra():
adj = [[] for _ in range(n)]
for u, v, w in edges:
if w != -1:
adj[u].append((v, w)); adj[v].append((u, w))
dist = [INF] * n
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (d + w, v))
return dist[destination]
for e in edges:
if e[2] == -1:
e[2] = 1
if dijkstra() > target:
return []
for e in edges:
if e[2] != 1:
continue
d = dijkstra()
if d <= target:
e[2] = 1 + target - d
if dijkstra() == target:
# fill the rest with a huge weight
for f in edges:
if f[2] == -1:
f[2] = target
return edges
return edges if dijkstra() == target else []function modifyGraphEdges(n, edges, source, destination, target) {
const INF = Infinity;
function dijkstra() {
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
if (w !== -1) { adj[u].push([v, w]); adj[v].push([u, w]); }
}
const dist = new Array(n).fill(INF);
dist[source] = 0;
const pq = [[0, source]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue;
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) { dist[v] = d + w; pq.push([d + w, v]); }
}
}
return dist[destination];
}
for (const e of edges) if (e[2] === -1) e[2] = 1;
if (dijkstra() > target) return [];
for (const e of edges) {
if (e[2] !== 1) continue;
const d = dijkstra();
if (d <= target) {
e[2] = 1 + target - d;
if (dijkstra() === target) return edges;
}
}
return dijkstra() === target ? edges : [];
}class Solution {
int n, source, destination;
int[][] edges;
long dijkstra() {
List<long[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges)
if (e[2] != -1) { adj[e[0]].add(new long[]{e[1], e[2]}); adj[e[1]].add(new long[]{e[0], e[2]}); }
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[source] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.offer(new long[]{0, source});
while (!pq.isEmpty()) {
long[] t = pq.poll();
long d = t[0]; int u = (int) t[1];
if (d > dist[u]) continue;
for (long[] nb : adj[u])
if (d + nb[1] < dist[(int) nb[0]]) {
dist[(int) nb[0]] = d + nb[1];
pq.offer(new long[]{dist[(int) nb[0]], nb[0]});
}
}
return dist[destination];
}
public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
this.n = n; this.edges = edges; this.source = source; this.destination = destination;
for (int[] e : edges) if (e[2] == -1) e[2] = 1;
if (dijkstra() > target) return new int[0][];
for (int[] e : edges) {
if (e[2] != 1) continue;
long d = dijkstra();
if (d <= target) {
e[2] = (int) (1 + target - d);
if (dijkstra() == target) return edges;
}
}
return dijkstra() == target ? edges : new int[0][];
}
}class Solution {
public:
int n, source, destination;
vector<vector<int>>* E;
long long dijkstra() {
vector<vector<pair<long long,int>>> adj(n);
for (auto& e : *E)
if (e[2] != -1) { adj[e[0]].push_back({e[2], e[1]}); adj[e[1]].push_back({e[2], e[0]}); }
vector<long long> dist(n, LLONG_MAX);
dist[source] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& nb : adj[u])
if (d + nb.first < dist[nb.second]) {
dist[nb.second] = d + nb.first;
pq.push({dist[nb.second], nb.second});
}
}
return dist[destination];
}
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
this->n = n; this->source = source; this->destination = destination; E = &edges;
for (auto& e : edges) if (e[2] == -1) e[2] = 1;
if (dijkstra() > target) return {};
for (auto& e : edges) {
if (e[2] != 1) continue;
long long d = dijkstra();
if (d <= target) {
e[2] = (int)(1 + target - d);
if (dijkstra() == target) return edges;
}
}
return dijkstra() == target ? edges : vector<vector<int>>{};
}
};Explanation
We control only the erased edges (weight -1); the fixed edges cannot change. The goal is to choose positive weights for the erased edges so the shortest distance from source to destination lands on target exactly.
The smallest influence each erased edge can have is weight 1. So we first set every erased edge to 1 and run Dijkstra. If even that minimum already exceeds target, no assignment can shrink it further and the task is impossible.
Otherwise we tune the erased edges one at a time. For each still-at-1 edge we measure the current shortest distance d. If d ≤ target, we bump this edge up by exactly the shortfall, 1 + target - d, nudging the best path that uses it up toward target.
We re-run Dijkstra after each change because raising one edge can reroute the shortest path elsewhere. As soon as a Dijkstra reports a distance equal to target, the configuration is valid and we return the edges; any erased edges left untouched stay harmless (large enough not to undercut target).
Example: with four erased edges between source 0 and destination 1, starting them at 1 gives a path shorter than 5; raising the right edge to absorb the gap of 5 yields an assignment like [[4,1,1],[2,0,4],[0,3,3],[4,3,1]] whose shortest 0→1 distance is exactly 5.