现在小强想从一个城市走到另一个不同的城市,并且每条边经过至多一次,同时他还有一个要求,起点和终点城市可以任意选择,但是等级必须是相同的。
但是小强不喜欢走特别远的道路,所以他想知道时间花费最小是多少。
进阶:时间复杂度,空间复杂度
第一行一个正整数 ,含义如题面所述。
第二行 个正整数 ,代表每个城市的等级。
接下来 行每行两个正整数 ,代表一条无向边。
保证给出的图是一棵树。
。
。
。
仅一行一个整数代表答案,如果无法满足要求,输出 。
3 1 2 1 1 2 2 3
2
结合以上大佬们给出的题解,遍历每一个节点,使用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; } }