修改图中的边权

class Solution {
public:
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>> &edges, int source, int destination, int target) {
        vector<pair<int, int>> g[n]; //邻接表
        for (int i = 0; i < edges.size(); i++) { // 遍历所有边
            int x = edges[i][0], y = edges[i][1];
            g[x].emplace_back(y, i);
            g[y].emplace_back(x, i); // 建图，额外记录边的编号，用于后面修改和返回
        }


        int dis[n][2], delta, vis[n]; 
    
        memset(dis, 0x3f, sizeof(dis));
        dis[source][0] = dis[source][1] = 0; //初始化初始节点距离
        auto dijkstra = [&](int k) { // 这里 k 表示第一次/第二次
            memset(vis, 0, sizeof(vis)); //初始都未访问
            for (;;) {//因为是连通图，跳出条件为找到目标值
                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 (auto [y, id]: g[x]) {  //遍历x的相邻边
                    int weight = edges[id][2];  //获取边的权值，这里要修正，但不修改，所以需要暂存，而不是直接使用权值去更新
                    if (weight == -1)  weight = 1; // -1 改成 1,第一次不直接在edge上改，防止丢失修改目标

                    if (k == 1 && edges[id][2] == -1) { //对于可以进行修正的边
                        // 第二次 Dijkstra，修正，是满足目标值
                        int w = delta + dis[y][0] - dis[x][1]; //修正的权值
                        if (w > weight)
                            edges[id][2] = weight = w; // 直接在 edges 上修改
                    }

                    // 更新最短路
                    dis[y][k] = min(dis[y][k], dis[x][k] + weight);
                }
            }
        };

        dijkstra(0);
        delta = target - dis[destination][0]; //还需要增加的值
        if (delta < 0) // -1 全改为 1 时，最短路比 target 还大
            return {};

        dijkstra(1);
        if (dis[destination][1] < target) // 最短路无法再变大，无法达到 target
            return {};

        for(auto&edge:edges) //按题目要求修改所有-1权值
            if(edge[2]==-1) edge[2] = 1;


        return edges;
    }
};