9.4 中兴通讯笔试面经 - 编程题 & 题解

考试平台： 海纳在线考试

考试时间： 2023-09-04

考试题型： 单选题10题（每题3分）+ 多选题5题（每题6分）+编程题2题（每题20分）

T1

题目描述

​ 在一个遥远的银河系中，存在一个强大的星际联盟。这个联盟由数十个星球组成，星球与星球之间的通讯依赖于穿梭于各星球之间的高科技飞船。在这个星际联盟中，由N个星球，分别编号为1到N。联盟首领需要向各个星球发送重要指令，而星球之间飞船的航行时间是确定的，例如从编号为1的星球到编号为3的星球，需要1小时来传递信息，我们可以将其记为(1,3,1)。进一步说，我们可以用(s,d,t)来表示从星球s到星球d所需要的时间t，并目将这些时间信息放入一个列表time中。注意，由于宇宙天体运动等因素，从星球A到星球B的时间并不一定等于从星球B到星球A的时间。

​ 现在，联盟首领正从他所在的 K 星球给其他星球发送一条命令，我们希望计算出至少需要多少时间才能使所有的星球都收到这个命令? 如果有的星球因为各种原因无法收到这条命令则返回-1.

1. N的范围在[1,100] 之间
2. K的范围在[1,N] 之间。
3. time 的长度在[1,6000]之间。
4. 所有的 timel =(s,d,t) 都有1 <= s,d <= N且1<= t <= 100。
5. 每个星球可同时派出多艘飞船前往其他星球

输入描述

第一行:N值，星球总数。K值，联盟首领当前所在的星球的编号，两个数用空格分隔; 第二行开始多行:每行3个值，表示星球之间的通信时间。 例如: 2 1 1，表示2号星球到1号星球的时间为1。

输出描述

至少需要多少小时才能使所有的星球都收到联盟首领的命令? 如果命令不能传递给全部星球，则返回-1.

样例

输入

4 2
2 1 1
2 3 1
3 4 1

输出

2

题解

BFS

输入和以往题目有所不同，以往题目输入都是已知（输入元素个数已知），这题没有限定输入元素个数（所以这里使用 while (scanner.hasNextInt()) ）。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(), K = scanner.nextInt();

        Airship[] airships = new Airship[N + 1];
        for (int i = 1; i <= N; i++) airships[i] = new Airship(i);

        while (scanner.hasNextInt()) {
            int s = scanner.nextInt(), d = scanner.nextInt(), t = scanner.nextInt();
            airships[s].addNeighbor(airships[d], t);
        }

        boolean[] vis = new boolean[N + 1];
        int maxTime = 0;

        // int[] {飞船编号, 时间}
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        queue.offer(new int[]{K, 0});
        vis[K] = true;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            Airship cur = airships[poll[0]];
            int now = poll[1];

            for (Map.Entry<Airship, Integer> entry : cur.neighbors.entrySet()) {
                Airship neighbor = entry.getKey();