Skip to content

899. Reachable Nodes In Subdivided Graph

899. Reachable Nodes In Subdivided Graph

题目: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/

难度: Hard

题意：

  1. 给定一张图，图上有无向边，边上有等距的点
  2. 从0出发，最长路径能够访问M个点，问总共能访问多少个点

思路：

  • 这个题是最短路的变种
  • 边上面点的个数就是边的权值，先做一遍最短路
  • 扫描每个边，判断左右两个端点的值，进行累加
  • 左/右 端点大于M的，不累加
  • 左/右 端点分别向边里面访问点，假设左端点能访问a个点，右端点能访问b个点，那么能访问的点数就是min(a + b, 该边点数)
  • 统计完边，再统计点，只需要扫描所有点，根据最短路的端点值，判断是否不大于M，累加
  • 最短路复杂度是o(n^2)，最短路中间有一个步骤，每一轮寻找当前最小的点开扩展，这一步骤是可以用一个堆来优化，复杂度是o(n log e)，e是边的个数。这个做法留给大家做练习

代码：

class Solution {
    private static int MAX = 2000000000;

    private class Edge {
        int src;
        int dest;
        int value;

        public Edge(int src, int dest, int value) {
            this.src = src;
            this.dest = dest;
            this.value = value;
        }
    }

    public int reachableNodes(int[][] edges, int M, int N) {
        List<Edge>[] edgeList = new List[N];
        for (int i = 0;i < edgeList.length;i++) {
            edgeList[i] = new ArrayList<Edge>();
        }

        for (int i = 0;i < edges.length;i++) {
            edgeList[edges[i][0]].add(new Edge(edges[i][0], edges[i][1], edges[i][2] + 1));
            edgeList[edges[i][1]].add(new Edge(edges[i][1], edges[i][0], edges[i][2] + 1));
        }

        int ret = 0;

        boolean[] flag = new boolean[N];
        int[] min = new int[N];
        for (int i = 0;i < N;i++) {
            flag[i] = false;
            min[i] = MAX;
        }

        min[0] = 0;
        while (true) {
            int idx = -1;
            for (int i = 0;i < N;i++) {
                if (!flag[i] && min[i] != MAX) {
                    if (idx == -1 || min[i] < min[idx]) {
                        idx = i;
                    }
                }
            }
            if (idx == -1) {
                break;
            }

            flag[idx] = true;
            for (int i = 0;i < edgeList[idx].size();i++) {
                Edge edge = edgeList[idx].get(i);
                if (!flag[edge.dest]) {
                    min[edge.dest] = Math.min(min[edge.dest], min[edge.src] + edge.value);
                }
            }
        }

        for (int i = 0;i < edges.length;i++) {
            if (min[edges[i][0]] + edges[i][2] <= M || min[edges[i][1]] + edges[i][2] <= M) {
                ret += edges[i][2];
                continue;
            }
            int left = 0, right = 0;
            if (min[edges[i][0]] <= M) {
                left = M - min[edges[i][0]];
            }
            if (min[edges[i][1]] <= M) {
                right = M - min[edges[i][1]];
            }
            if (left + right >= edges[i][2]) {
                ret += edges[i][2];
            } else {
                ret += left + right;
            }
        }

        for (int i = 0;i < N;i++) {
            if (min[i] <= M) {
                ret++;
            }
        }

        return ret;
    }
}
回到顶部