2699. 修改图中的边权 (opens new window)

1.迪杰斯特拉

本题难点在于，应该采取什么样的策略修改权值，修改任意一条边都会改变起点到目标节点的最短路径，因此每修改一个值都需要计算一次当前的最短路径。求图的最短路径使用迪杰斯特拉算法，题目给的图并不是邻接表的形式存储，因此每次修改边的权值都需要转化为邻接图。这里给出一个关键例子：

整体流程可以分为两个步骤：

• 判断解是否存在：首先将所有-1的边权值设置为1，并通过迪杰斯特拉算法计算最短路径，如果大于target则无解；然后再将所有-1的边权值设置为target，再用一次迪杰斯特拉，如果最短路径小于terget也无解。

• 二分法枚举搜索：每条边的权值可能的取值范围在【1，target】之间，使用二分法枚举可修改边权值【1，1，1...】到【target，target，target...】之间的所有结果。

• ✨搜索空间大小为k*(target-1)，其中k为可修改边的数量，即：

  • 【1，1，...，1】

  • 【2，1，...，1】

  • 【3，1，...，1】

  • ...

  • 【D，1，...，1】

  • 【D，2，...，1】

  • ...

  • 【D，D，...，D】

  使用二分枚举的核心在于理解为什么此处搜索空间大小不是(target-1)的k次方，也就是说搜索时忽略【1，5】是否会错过唯一解？下面以列号作为边的索引展开讨论，从小到大枚举第i个边的权值时(假设第i条边在最短路径内)，前i-1条边有如下两种情况：

  • 如果前i-1条边并不在最短路径内，那么它们的权值为多少并不会影响到最小路径和，只需要修改第i条边即可。
  • 而如果第i-1条边会影响到最短路径，那么第i-1条边和第i条边权值为【a，b】或者是【b，a】都是等效的。

  综上这种递增的搜索方式并不会错过唯一解。例子：假设s(起点)到e(终点)只有二号边，target为5，那么显然边权值为【target,5】和【1，5】是等价的。而如果s到e最短路径有一号和二号边，那么【5，1】和【1，5】的最短路径和是相同的(题目只需要给出一种修改组合，实际上【3，3】,【4，2】都是等同的)。

class Solution {
  public  int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        int k = 0;
        for (int[] edge : edges) {
            if(edge[2]==-1) k++;
        }
        //判断是否存在解
        if (dijks(source, destination, construct(n, edges, 0, target)) > target){
            return new int[0][];
        }
        if (dijks(source, destination, construct(n, edges, (long)k * (target - 1), target)) < target) {
            return new int[0][];
        }
        long left = 0, right = (long)k * (target - 1);
        long mid = (left + right) / 2;
        while(left<right){
            mid = (left + right) / 2;
            long min = dijks(source, destination, construct(n, edges, mid, target));
            if(min<target) left = mid + 1;
            else right = mid;
        }
        int[][] dis = construct(n, edges, left, target);
        for (int[] edge : edges) {
            edge[2] = dis[edge[0]][edge[1]];
        }
        return edges;
    }

    public  long dijks(int source, int destination, int[][] mat) {
        long[] dis = new long[mat.length];
        Arrays.fill(dis, Integer.MAX_VALUE/2);
        boolean[] used = new boolean[mat.length];
        dis[source]=0;
        for (int i = 0; i < mat.length-1; i++) {
            int minindx = -1;
            for (int j = 0; j < mat.length; j++) {
                //minindx初始化为第一个没有使用过的节点
                if (!used[j] && (minindx == -1 || dis[j] < dis[minindx])) {
                    minindx = j;
                }
            }
            //拿到当前轮次最小路径长度的节点
            used[minindx] = true;

            for (int j = 0; j < mat.length; j++) {
                //为-1说明不可达
                if (!used[j]&&mat[minindx][j]!=-1) {
                    long path = dis[minindx] + mat[minindx][j];
                    dis[j] = Math.min(dis[j], path);
                }
            }
        }
        return dis[destination];
    }

    public  int[][] construct(int n, int[][] edges, long idx, int target) {
        int[][] mat = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(mat[i], -1);
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (w != -1) {
                mat[u][v] = mat[v][u] = w;
            } else {
                if (idx >= target - 1) {
                    mat[u][v] = mat[v][u] = target;
                    idx -= (target - 1);
                } else {
                    mat[u][v] = mat[v][u] = (int) (1 + idx);
                    idx = 0;
                }
            }
        }
        return mat;
    }
}