首页 > 试题广场 >

树上最短链

[编程题]树上最短链

热度指数：2414 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个地区有 $\mathit n$ 个城市以及 $\mathit n-1$ 条无向边，每条边的时间边权都是 $\text 1$ ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。
现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。

但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

进阶：时间复杂度 $O(n^2logn)\$ ，空间复杂度 $O(n)\$

输入描述:

第一行一个正整数 ，含义如题面所述。
第二行  个正整数 ，代表每个城市的等级。
接下来  行每行两个正整数 ，代表一条无向边。
保证给出的图是一棵树。
 。
 。
。

输出描述:

仅一行一个整数代表答案，如果无法满足要求，输出  。

示例1

输入

输出

算法知识视频讲解

Java

霸王龙v2

结合以上大佬们给出的题解，遍历每一个节点，使用bfs寻找任意两节点的最短路径。题目中增加限制条件：节点要在同一级，所以使用领接表存储每个节点相连的节点。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] grade = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            grade[i] = in.nextInt();
        }
        List> edges = new ArrayList();
        for (int i = 0; i <= n; i++) {
            edges.add(new ArrayList());
        }
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            // 双向边
            edges.get(u).add(v);
            edges.get(v).add(u);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            min = Math.min(min, bfs(edges, grade, i));
        }
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
    private static int bfs(List> edges, int[] grade, int st) {
        Queue queue = new LinkedList();
        int n = grade.length;
        boolean[] marked = new boolean[n];
        queue.add(st);
        marked[st] = true;
        int cur = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            cur++;
            while (size-- > 0) {
                int t = queue.poll();
                for (int x : edges.get(t)) {
                    if (marked[x]) continue;
                    if (grade[x] == grade[st])
                        return cur;
                    queue.add(x);
                    marked[x] = true;
                }
            }
        }
        return Integer.MAX_VALUE;
    }
}

发表于 2022-04-19 22:48:34 回复(0)