问题描述

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。

图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边，cnti 是将边 细分 后的新节点总数。注意，cnti == 0 表示边不可细分。

要 细分 边 [ui, vi] ，需要将其替换为 (cnti + 1) 条新边，和 cnti 个新节点。新节点为 x1, x2, ..., xcnti ，新边为 [ui, x1], [x1, x2], [x2, x3], ..., [xcnti+1, xcnti], [xcnti, vi] 。

现在得到一个 新的细分图 ，请你计算从节点 0 出发，可以到达多少个节点？如果节点间距离是 maxMoves 或更少，则视为 可以到达 。

给你原始图和 maxMoves ，返回 新的细分图中从节点 0 出发 可到达的节点数 。

提示：

• 0 <= edges.length <= min(n * (n - 1) / 2, 104)
• edges[i].length == 3
• 0 <= ui < vi < n
• 图中 不存在平行边
• 0 <= cnti <= 104
• 0 <= maxMoves <= 109
• 1 <= n <= 3000

示例：

示例1：

输入：edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
输出：13
解释：边的细分情况如上图所示。
可以到达的节点已经用黄色标注出来。

示例2：

输入：edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
输出：23

示例3：

输入：edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
输出：1
解释：节点 0 与图的其余部分没有连通，所以只有节点 0 可以到达。

解题思路

这个题目考察的主要是图的遍历以及最短路径的求解。首先，图的遍历方法主要有广度优先搜索（BFS）和深度优先搜索（DFS）两种，在本题中，这两种方法都可。接着我们可以将问题转化为，判断从节点0出发，是否可以抵达节点n，并计算节点0到达节点n的最短距离。值得注意的是，这里限制了节点0与其它节点的最大长度。

常用的计算指定节点到达其它节点的最短距离的算法是迪杰斯特拉算法（Dijkstra），Dijkstra的最大缺点是当边的权值为负时无法计算，但在本题中不受影响。

假设我们已经找到了节点0到达其它节点的最短距离，我们只需再对图进行一次遍历，并计算每条可达边以及不可达边的长度。代码如下：

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        int node;
        int dis;
        set<int> s;
        int cnt = 1;
        queue<int> nodes;
        vector<bool> unvisited(n, true);
        vector<int> distance(n, 0x7fffffff);
        vector<vector<int>> matrix(n, vector<int>(n, -1));
        for(int i = 0; i < edges.size(); i++){
            matrix[edges[i][0]][edges[i][1]] = edges[i][2];
            matrix[edges[i][1]][edges[i][0]] = edges[i][2];
        }
        s.insert(0);
        nodes.push(0);
        distance[0] = 0;
        unvisited[0] = false;
        while(nodes.size() > 0){
            node = nodes.front();
            nodes.pop();
            s.erase(node);
            for(int i = 0; i < n; i++){
                if(matrix[node][i] >= 0){
                    dis = distance[node] + matrix[node][i] + 1;
                    if(dis <= maxMoves){
                        cnt += matrix[node][i] + unvisited[i];
                        matrix[i][node] = 0;
                        matrix[node][i] = 0;
                        unvisited[i] = false;
                        if(distance[i] > dis){
                            distance[i] = dis;
                            if(!s.count(i)){
                                nodes.push(i);
                                s.insert(i);
                            }
                        }
                    }
                }
            }
        }
        s.clear();
        s.insert(0);
        nodes.push(0);
        while(nodes.size()){
            node = nodes.front();
            nodes.pop();
            for(int i = 0; i < n; i++){
                if(matrix[node][i] >= 0){
                    dis = distance[node] + matrix[node][i] + 1;
                    if(dis <= maxMoves){
                        cnt += matrix[node][i] + unvisited[i];
                        matrix[i][node] = -1;
                        unvisited[i] = false;
                        if(!s.count(i)){
                            s.insert(i);
                            nodes.push(i);
                        }
                    }
                    else{
                        cnt += (maxMoves - distance[node]);
                        matrix[i][node] -= (maxMoves - distance[node]);
                    }
                }
            }
        }
        return cnt;
    }
};

按照上述方法来设计代码，最大的问题是算法复杂度过高，容易超时。

原文地址：http://www.cnblogs.com/greatestchen/p/16928379.html