修改图中的边权【LC2699】
给你一个
n个节点的 无向带权连通 图，节点编号为0到n - 1，再给你一个整数数组edges，其中edges[i] = [ai, bi, wi]表示节点ai和bi之间有一条边权为wi的边。部分边的边权为
-1（wi = -1），其他边的边权都为 正 数（wi > 0）。你需要将所有边权为
-1的边都修改为范围[1, 2 * 109]中的 正整数 ，使得从节点source到节点destination的 最短距离 为整数target。如果有 多种
修改方案可以使 source 和 destination 之间的最短距离等于 target ，你可以返回任意一种方案。
如果存在使 source 到 destination 最短距离为 target 的方案，请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 空数组 。
**注意：**你不能修改一开始边权为正数的边。
这两天为啥那么难
- 思路
- 此时还存在一种情况：如果修改完所有的值，最短路径仍小于
target，此时也返回空数组
- 实现
- 由于最后需要更改数组中的权值，因此构建邻接数组时需要记录边的下标
class Solution { public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) { List<int[]> g[] = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); for (int i = 0; i < edges.length; i++) { int x = edges[i][0], y = edges[i][1]; g[x].add(new int[]{y, i}); g[y].add(new int[]{x, i}); // 建图，额外记录边的编号 } var dis = new int[n][2]; for (int i = 0; i < n; i++) if (i != source) dis[i][0] = dis[i][1] = Integer.MAX_VALUE; dijkstra(g, edges, destination, dis, 0, 0); int delta = target - dis[destination][0]; if (delta < 0) // -1 全改为 1 时，最短路比 target 还大 return new int[][]{}; dijkstra(g, edges, destination, dis, delta, 1); if (dis[destination][1] < target) // 最短路无法再变大，无法达到 target return new int[][]{}; for (var e : edges) if (e[2] == -1) // 剩余没修改的边全部改成 1 e[2] = 1; return edges; } // 朴素 Dijkstra 算法 // 这里 k 表示第一次/第二次 private void dijkstra(List<int[]> g[], int[][] edges, int destination, int[][] dis, int delta, int k) { int n = g.length; var vis = new boolean[n]; for (; ; ) { // 找到当前最短路，去更新它的邻居的最短路 // 根据数学归纳法，dis[x][k] 一定是最短路长度 int x = -1; for (int i = 0; i < n; ++i) if (!vis[i] && (x < 0 || dis[i][k] < dis[x][k])) x = i; if (x == destination) // 起点 source 到终点 destination 的最短路已确定 return; vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度 for (var e : g[x]) { int y = e[0], eid = e[1]; int wt = edges[eid][2]; if (wt == -1) wt = 1; // -1 改成 1 if (k == 1 && edges[eid][2] == -1) { // 第二次 Dijkstra，改成 w int w = delta + dis[y][0] - dis[x][1]; if (w > wt) edges[eid][2] = wt = w; // 直接在 edges 上修改 } // 更新最短路 dis[y][k] = Math.min(dis[y][k], dis[x][k] + wt); } } } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/modify-graph-edge-weights/solutions/2278296/xiang-xi-fen-xi-liang-ci-dijkstrachou-mi-gv1m/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
