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;
    }
}


回到顶部