2699.修改图中的边权.md

2699.修改图中的边权

/*
 * @lc app=leetcode.cn id=2699 lang=typescript
 *
 * [2699] 修改图中的边权
 */

// @lc code=start
function modifiedGraphEdges(
  n: number,
  edges: number[][],
  source: number,
  destination: number,
  target: number,
): number[][] {}
// @lc code=end

解法 1: 多次最短路

const floyd = (n: number, edges: number[][]) => {
  const g: number[][] = Array.from({ length: n }, () => new Array(n).fill(Infinity))
  for (let [u, v, w] of edges) {
    if (w !== -1) g[u][v] = g[v][u] = w
  }
  for (let i = 0; i < n; i++) g[i][i] = 0
  // floyd
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        g[j][k] = Math.min(g[j][k], g[j][i] + g[i][k])
      }
    }
  }
  return g
}
function modifiedGraphEdges(
  n: number,
  edges: number[][],
  source: number,
  destination: number,
  target: number,
): number[][] {
  const g: number[][] = Array.from({ length: n }, () => new Array(n).fill(Infinity))
  for (let [u, v, w] of edges) {
    g[u][v] = g[v][u] = w
  }
  for (let i = 0; i < n; i++) g[i][i] = 0
  const g1 = floyd(n, edges)
  if (g1[source][destination] < target) return []

  const dist = new Array(n).fill(Infinity),
    vis: number[] = []
  dist[source] = 0
  out: for (let i = 0; i < n; i++) {
    let t = -1
    for (let j = 0; j < n; j++) {
      if (!vis[j] && (t === -1 || dist[t] > dist[j])) t = j
    }
    if (t === -1) break
    vis[t] = 1
    for (let j = 0; j < n; j++) {
      if (vis[j] || g[t][j] === Infinity) continue
      if (g[t][j] === -1) {
        const a = dist[t],
          b = g1[destination][j]
        if (a + b < target) {
          g[t][j] = g[j][t] = target - a - b
          break out
        } else {
          g[t][j] = g[j][t] = 1
          dist[j] = Math.min(dist[j], dist[t] + 1)
        }
      }
      dist[j] = Math.min(dist[j], dist[t] + g[j][t])
    }
  }
  for (let edge of edges) {
    const [u, v, w] = edge
    if (w === -1) {
      if (g[u][v] !== -1) {
        edge[2] = g[u][v]
      } else {
        edge[2] = 2e9
      }
    }
  }
  const g2 = floyd(n, edges)
  if (g2[source][destination] !== target) return []
  return edges
}

Case

test.each([
  {
    input: {
      n: 4,

      edges: [
        [0, 1, 1],
        [1, 2, 2],
        [2, 3, 3],
      ],
      source: 0,
      destination: 2,
      target: 1,
    },
    output: [],
  },
  {
    input: {
      n: 10,

      edges: [
        [7, 0, 68],
        [1, 2, 61],
        [2, 9, 16],
        [4, 7, 95],
        [7, 6, -1],
        [6, 5, 73],
        [8, 5, 42],
        [5, 3, 21],
        [9, 3, 13],
        [5, 1, -1],
        [8, 3, 78],
        [5, 7, -1],
        [6, 9, 38],
        [0, 8, 26],
        [0, 6, -1],
        [4, 8, 68],
        [9, 5, 52],
        [8, 2, 90],
        [7, 8, 37],
      ],
      source: 0,
      destination: 1,
      target: 122,
    },
    output: [
      [7, 0, 68],
      [1, 2, 61],
      [2, 9, 16],
      [4, 7, 95],
      [7, 6, 1000000005],
      [6, 5, 73],
      [8, 5, 42],
      [5, 3, 21],
      [9, 3, 13],
      [5, 1, 54],
      [8, 3, 78],
      [5, 7, 1000000005],
      [6, 9, 38],
      [0, 8, 26],
      [0, 6, 119],
      [4, 8, 68],
      [9, 5, 52],
      [8, 2, 90],
      [7, 8, 37],
    ],
  },
  {
    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],
    ],
  },
  {
    input: {
      n: 3,
      edges: [
        [0, 1, -1],
        [0, 2, 5],
      ],
      source: 0,
      destination: 2,
      target: 6,
    },
    output: [],
  },
  {
    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],
    ],
  },
])(
  'input: n = $input.n, edges = $input.edges, source = $input.source, destination = $input.destination, target = $input.target',
  ({ input: { n, edges, source, destination, target }, output }) => {
    const newEdges = modifiedGraphEdges(n, edges, source, destination, target)
    if (output.length === 0) {
      expect(newEdges.length).toBe(0)
    } else {
      const g = floyd(n, newEdges)
      expect(g[source][destination]).toEqual(target)
    }
  },
)