modifiedGraphEdges.js

function modifiedGraphEdges(n, edges, source, destination, target) {
  const finalize = (m, edges) => {
    for (let e of edges) {
      if (e[2] < 0) {
        if (m > 0) {
          --m;
          e[2] = 1;
        } else {
          e[2] = 1234567890;
        }
      }
    }
  }

  const spfa = (n, s, con) => {
    let d = Array(n).fill(-1);
    let mark = Array(n).fill(false);
    d[s] = 0;
    let q = [[0, s]];
    while (q.length > 0) {
      let x = q.pop()[1];
      if (mark[x]) {
        continue;
      }
      mark[x] = true;
      for (let v of con[x]) {
        let y = v[0], w = v[1];
        if (mark[y] || (d[y] >= 0 && d[y] <= d[x] + w)) {
          continue;
        }
        d[y] = d[x] + w;
        q.push([-d[y], y]);
        q.sort((a, b) => a[0] - b[0]);
      }
    }
    return d;
  }

  let ind = [];
  for (let i = 0; i < edges.length; ++i) { 
    if (edges[i][2] < 0) {
      ind.push(i);
    }
  }

  let left = 0, right = ind.length;
  while (left <= right) {
    let mid = left + ((right - left) >> 1);
    let con = Array.from({length: n}, () => []);
    let m = mid;
    for (let e of edges) {
      let w = e[2];
      if (e[2] < 0) {
        if (m <= 0) {
          continue;
        }
        --m;
        w = 1;
      }   
      con[e[0]].push([e[1], w]);
      con[e[1]].push([e[0], w]);
    }
    let d1 = spfa(n, source, con);
    if (d1[destination] == target) {
      finalize(mid, edges);
      return edges;
    }
    if (d1[destination] >= 0 && d1[destination] < target) {
      right = mid - 1;
      continue;
    }
    let d2 = spfa(n, destination, con);
    for (let t = mid; t < ind.length; ++t) {
      let i = ind[t];
      if (d1[edges[i][0]] >= 0 && d2[edges[i][1]] >= 0 && d1[edges[i][0]] + d2[edges[i][1]] < target) {
        edges[i][2] = target - (d1[edges[i][0]] + d2[edges[i][1]]);
        finalize(mid, edges);
        return edges;
      } 
      if (d1[edges[i][1]] >= 0 && d2[edges[i][0]] >= 0 && d1[edges[i][1]] + d2[edges[i][0]] < target) {
        edges[i][2] = target - (d1[edges[i][1]] + d2[edges[i][0]]);
 finalize(mid, edges);
        return edges;
      }
    }
    left = mid + 1;
  }

  return [];
}