题目描述

从具有 0 到 N-1 的结点的无向图（“原始图”）开始，对一些边进行细分。

该图给出如下：edges[k] 是整数对 (i, j, n) 组成的列表，使 (i, j) 是原始图的边。

n 是该边上新结点的总数

然后，将边 (i, j) 从原始图中删除，将 n 个新结点 (x_1, x_2, ..., x_n) 添加到原始图中，

将 n+1 条新边 (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j) 添加到原始图中。

现在，你将从原始图中的结点 0 处出发，并且每次移动，你都将沿着一条边行进。

返回最多 M 次移动可以达到的结点数。

样例

输入：edges = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3
输出：13
解释：
在 M = 6 次移动之后在最终图中可到达的结点如下所示。

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

注意

1. 0 <= edges.length <= 10000
2. 0 <= edges[i][0] < edges[i][1] < N
3. 不存在任何 i != j 情况下 edges[i][0] == edges[j][0] 且 edges[i][1] == edges[j][1]。
4. 原始图没有平行的边。
5. 0 <= edges[i][2] <= 10000
6. 0 <= M <= 10^9
7. 1 <= N <= 3000
8. 一个可到达结点是从结点 0 使用最多 M 次移动可以到达的点。

算法

(最短路) $O((n + m) \log m)$

1. 将添加的结点数 + 1 作为原图边的路径长度，然后以 0 号点为起点，求单源最短路。
2. 假设求得的最短路数组为 dis。统计 dis[x] <= M 的结点 x，这些都可以作为可到达结点。
3. 然后枚举每一条边，如果边的两个端点都可到达，则答案加上 min(edge[i][2], 2 * M - dis[x] - dis[y])；如果只有结点 x 可以到达，则答案加上 min(edge[i][2], M - dis[x])；结点 y 可以到达同理。

时间复杂度

• 采用 dijkstra 算法，求最短路的时间复杂度为 $O((n + m) \log m)$，其中 n 为点数，m 为边数。然后需要遍历每个点和每条边，故总时间复杂度为 $O((n + m) \log m)$。

空间复杂度

• 需要额外的数组来存图，以及记录最短距离，采用 dijkstra 算法需要额外的堆空间，故总空间复杂度为 $O(n + m)$。

C++ 代码

struct Node {
    int x, d;
    Node(int x_, int d_): x(x_), d(d_){}
    bool operator < (const Node &v) const {
        return d > v.d;
    }
};

class Solution {
public:

    void dijkstra(const vector<vector<pair<int, int>>>& e, int N, vector<int>& dis) {
        priority_queue<Node> heap;
        dis[0] = 0;
        heap.push(Node(0, 0));

        while (!heap.empty()) {

            Node sta(heap.top());
            heap.pop();

            if (sta.d > dis[sta.x])
                continue;

            for (auto edge : e[sta.x]) {
                if (dis[edge.first] > dis[sta.x] + edge.second) {
                    dis[edge.first] = dis[sta.x] + edge.second;
                    heap.push(Node(edge.first, dis[edge.first]));
                }
            }
        }
    }

    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        int m = edges.size();
        const int inf = 200000000;
        vector<vector<pair<int, int>>> e(m);

        for (auto edge : edges) {
            e[edge[0]].emplace_back(make_pair(edge[1], edge[2] + 1));
            e[edge[1]].emplace_back(make_pair(edge[0], edge[2] + 1));
        }

        vector<int> dis(N, inf);
        dijkstra(e, N, dis);

        int ans = 0;
        for (int i = 0; i < N; i++)
            if (dis[i] <= M)
                ans++;

        for (auto edge : edges) {
            int x = edge[0], y = edge[1];
            if (dis[x] <= M && dis[y] <= M)
                ans += min(edge[2], 2 * M - dis[x] - dis[y]);
            else if (dis[x] <= M && dis[y] > M)
                ans += min(edge[2], M - dis[x]);
            else if (dis[y] <= M && dis[x] > M)
                ans += min(edge[2], M - dis[y]);
        }
        return ans;
    }
};