修改图中的边权

题目

2699. 修改图中的边权

---

给你一个 n 个节点的 无向带权连通 图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。

部分边的边权为 -1（wi = -1），其他边的边权都为 正 数（wi > 0）。

你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 10^9] 中的 正整数 ，使得从节点 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 <= 100
• 1 <= edges.length <= n * (n - 1) / 2
• edges[i].length == 3
• 0 <= ai, bi < n
• wi = -1 或者 1 <= wi <= 10^7
• ai != bi
• 0 <= source, destination < n
• source != destination
• 1 <= target <= 10^9
• 输入的图是连通图，且没有自环和重边。

题解

方法一：

思路

dijkstra的高级应用

对于答案不可能的情况有两种，修改边权全为1，但是最短路却大于target，修改边权全为无穷，但是最短路小于target。
这两种情况可以通过dijkstra来判断。

若起点为s，终点为e。

先求出所有可修改边修改为1的以s为源点的单源最短路径dis，$dis_i$为点i到点s的最短路径。

随后再次dijkstra，求s为源点的单源最短路径dis2。本次dijkstra需要动态修改边权使得s到e的最短路径为target。

如何动态修改边权？

设点x和y之间的边权为-1，若其边权需要动态修改为w。则w满足$dis2_x + w + dis_e - dis_y = target$。
此外由于边权修改最小值为1，所以$w = max(1,target-dis_e+dis_y-dis2_x)$

在第二次dijkstra后对于没有修改的-1边权显然是不会参与最短路的，所以修改为任意正值即可。

代码

#define N 105
#define INF 0x3f3f3f3f
int g[N][N]; // memset(g, 0x3f, sizeof(g));
int dis[N], vis[N];
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = 0, mind = INF;
        for (int j = 0; j < n; j++)
            if (!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = 1;
        for (int v = 0; v < n; v++) {
            if (v == u) continue;
            if (dis[v] > dis[u] + g[u][v])
                dis[v] = dis[u] + g[u][v];
        }
    }
}

class Solution {
public:
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int src, int dst, int target) {
        memset(g, 0x3f, sizeof(g));
        for (auto& i:edges) {
            g[i[0]][i[1]] = g[i[1]][i[0]] = i[2];
            if (i[2] == -1) g[i[0]][i[1]] = g[i[1]][i[0]] = INF;
        }
        dijkstra(n, src);
        if (dis[dst] < target) return {};

        memset(g, 0x3f, sizeof(g));
        for (auto& i:edges) {
            g[i[0]][i[1]] = g[i[1]][i[0]] = i[2];
            if (i[2] == -1) g[i[0]][i[1]] = g[i[1]][i[0]] = 1;
        }
        dijkstra(n, src);
        if (dis[dst] > target) return {};
        memset(g, 0x3f, sizeof(g));
        for (auto& i:edges) {
            g[i[0]][i[1]] = g[i[1]][i[0]] = i[2];
        }
        vector<int> dis2(n, INF);
        dis2[src] = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            int u = 0, mind = INF;
            for (int j = 0; j < n; j++)
                if (!vis[j] && dis2[j] < mind)
                    u = j, mind = dis2[j];
            vis[u] = 1;
            for (int v = 0; v < n; v++) {
                if (v == u) continue;
                if (g[u][v] == -1)
                    g[v][u] = g[u][v] = max(1, target - dis2[u] - dis[dst] + dis[v]);
                if (dis2[v] > dis2[u] + g[u][v])
                    dis2[v] = dis2[u] + g[u][v];
                
            }
        }
        for (auto& i:edges) {
            i[2] = g[i[0]][i[1]];
            if (i[2] == -1) i[2] = 1;
        }
        return edges;
    }
};

方法二：

思路

二分+dijstra。

首先排除答案不可能的情况。

对于最短路径上需要修改的边权，修改后的所有边权的任意两条的差值可以不超过1。

而不在最短路径上却需要修改的边权，其实可以任意取值（只要取值后不在最短路上）。

假设给出的图中有ncnt条-1权的边。若所有修改权值后的边的权值和为m，我们可以按照固定顺序给m%ncnt条边权修改为m/ncnt+1,剩余的边权修改为m/ncnt。

然后通过djkstra求最短路径dis。

显然会发现随着m的增大dis也会增大。于是在单调函数上用二分法求出使得dis等于target的m，然后再模拟分配一下需要修改的边权便可得到答案。

代码

#define N 105
#define INF 0x3f3f3f3f3f3f3f3f
long g[N][N]; // memset(g, 0x3f, sizeof(g));
long dis[N], vis[N];
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (int i = 0; i < n; i++) {
        long u = 0, mind = INF;
        for (int j = 0; j < n; j++)
            if (!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = 1;
        for (int v = 0; v < n; v++) {
            if (v == u) continue;
            if (dis[v] > dis[u] + g[u][v])
                dis[v] = dis[u] + g[u][v];
        }
    }
}

class Solution {
public:
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int src, int dst, int target) {
        memset(g, 0x3f, sizeof(g));
        for (auto& i:edges) {
            g[i[0]][i[1]] = g[i[1]][i[0]] = i[2];
            if (i[2] == -1) g[i[0]][i[1]] = g[i[1]][i[0]] = INF;
        }
        dijkstra(n, src);
        if (dis[dst] < target) return {};

        memset(g, 0x3f, sizeof(g));
        for (auto& i:edges) {
            g[i[0]][i[1]] = g[i[1]][i[0]] = i[2];
            if (i[2] == -1) g[i[0]][i[1]] = g[i[1]][i[0]] = 1;
        }
        dijkstra(n, src);
        if (dis[dst] > target) return {};

        auto dj = [&](long a, long b) {
            memset(g, 0x3f, sizeof(g));
            for (auto& i:edges) {
                g[i[0]][i[1]] = g[i[1]][i[0]] = i[2];
            }
            memset(vis, 0, sizeof(vis));
            memset(dis, 0x3f, sizeof(dis));
            dis[src] = 0;
            for (int i = 0; i < n; i++) {
                long u = 0, mind = INF;
                for (int j = 0; j < n; j++)
                    if (!vis[j] && dis[j] < mind)
                        u = j, mind = dis[j];
                vis[u] = 1;
                for (int v = 0; v < n; v++) {
                    if (v == u) continue;
                    if (g[u][v] == -1) {
                        g[u][v] = g[v][u] = a;
                        if (b) {
                            g[u][v] = g[v][u] = a+1;
                            b--;
                        }
                    }
                    if (dis[v] > dis[u] + g[u][v])
                        dis[v] = dis[u] + g[u][v];
                }
            }
        };

        int ncnt = 0;
        for (auto& i:edges) {
            if (i[2] == -1) ncnt++;
        }
        
        long l = ncnt, r = ncnt*1e10;
        while (l<r) {
            long m = l+r>>1;
            long a = m/ncnt, b = m%ncnt;
            dj(a, b);
            // cout << dis[dst] << " " << target << "\n";
            if (dis[dst] >= target) r = m;
            else l = m+1;
        }
        if (ncnt) dj(r/ncnt, r%ncnt);
        // cout << dis[dst] << " " << target << "\n";
        for (auto& i:edges) {
            i[2] = g[i[0]][i[1]];
            if (i[2] == -1) i[2] = 1;
        }
        return edges;
    }
};