Skip to content

Latest commit

 

History

History
178 lines (136 loc) · 5.77 KB

README.md

File metadata and controls

178 lines (136 loc) · 5.77 KB

2359. 找到离给定两个节点最近的节点

English Version

题目描述

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

 

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

 

提示：

  • n == edges.length
  • 2 <= n <= 105
  • -1 <= edges[i] < n
  • edges[i] != i
  • 0 <= node1, node2 < n

解法

方法一：枚举公共点

最短路问题。

枚举 $node1$，$node2$ 到某个公共点 $p$ 的距离较大值，求最小的距离即可。

最小距离可以用 $dijkstra$ 算法求得。

相似题目：2203.得到要求路径的最小带权子图

Python3

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        def dijkstra(g, u):
            dist = [inf] * n
            dist[u] = 0
            q = [(0, u)]
            while q:
                d, u = heappop(q)
                if d > dist[u]:
                    continue
                for v in g[u]:
                    if dist[v] > dist[u] + 1:
                        dist[v] = dist[u] + 1
                        heappush(q, (dist[v], v))
            return dist

        g = defaultdict(list)
        n = len(edges)
        for i, v in enumerate(edges):
            if v != -1:
                g[i].append(v)
        d1 = dijkstra(g, node1)
        d2 = dijkstra(g, node2)
        d = inf
        ans = -1
        for i, (a, b) in enumerate(zip(d1, d2)):
            if d > max(a, b):
                d = max(a, b)
                ans = i
        return ans

Java

class Solution {
    private static final int INF = 0x3f3f3f3f;

    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; ++i) {
            if (edges[i] != -1) {
                g[i].add(edges[i]);
            }
        }
        int[] d1 = dijkstra(g, node1);
        int[] d2 = dijkstra(g, node2);
        int d = INF;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            int t = Math.max(d1[i], d2[i]);
            if (d > t) {
                d = t;
                ans = i;
            }
        }
        return ans;
    }

    private int[] dijkstra(List<Integer>[] g, int u) {
        int n = g.length;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[u] = 0;
        PriorityQueue<Pair<Integer, Integer>> q
            = new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
        q.offer(new Pair<>(0, u));
        while (!q.isEmpty()) {
            Pair<Integer, Integer> p = q.poll();
            int d = p.getKey();
            u = p.getValue();
            if (d > dist[u]) {
                continue;
            }
            for (int v : g[u]) {
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    q.offer(new Pair<>(dist[v], v));
                }
            }
        }
        return dist;
    }
}

TypeScript



...