华为机试：最小传输时延

【编程题目 | 200分】最小传输时延 [ 200 / 中等 ]

题目描述

• 某通信网络中有N个网络结点，用1到N进行标识。网络通过一个有向无环图表示，其中图的边的值表示结点之间的消息传递时延。
• 现给定相连节点之间的时延列表times[i]={u，v，w}，其中u表示源结点，v表示目的结点，w表示u和v之间的消息传递时延。
• 请计算给定源结点到目的结点的最小传输时延，如果目的结点不可达，返回-1。

注：

1. N的取值范围为[1，100];
2. 时延列表times的长度不超过6000，且 1 <= u,v <= N，0 <= w <= 100;

输入描述

1. 输入的第一行为两个正整数，分别表示网络结点的个数N，以及时延列表的长度M，用空格分隔；
2. 接下来的M行为两个结点间的时延列表[u v w];
3. 输入的最后一行为两个正整数，分别表示源结点和目的结点。

输出描述

起点到终点得最小时延，不可达则返回-1

示例

输入

3 3
1 2 11
2 3 13
1 3 50
1 3
1
2
3
4
5

输出

24
1

思路分析

典型的有向图的单源最短路径，可以使用Dijkstra算法计算起点到终点的最短时延。

使用优先队列实现算法中每次取最短路径。

提供两种连接关系的表示方法，包括邻接表和邻接矩阵。

注：邻接矩阵表示的时候，不要赋值Integer.MAX_VALUE，会溢出，+1，变为负数

可以参考：【Leetcode】图算法总结

代码实现

邻接表

import java.util.*;

public class minLatency {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] times = new int[M][3];
        for (int i = 0; i < M; i++) {
            times[i][0] = in.nextInt();
            times[i][1] = in.nextInt();
            times[i][2] = in.nextInt();
        }
        int start = in.nextInt();
        int end = in.nextInt();
        
        // Dijkstra算法，邻接表
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        queue.add(new int[]{start, 0});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int node = poll[0];
            for (int i = 0; i < times.length; i++) {
                if (times[i][0] == node) {
                    int next = times[i][1];
                    if (dist[next] > dist[node] + times[i][2]) {
                        dist[next] = dist[node] + times[i][2];
                        queue.add(new int[]{next, dist[next]});
                    }
                }
            }
        }
        if (dist[end] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(dist[end]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

邻接矩阵

import java.util.*;

public class minLatency {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] times = new int[M][3];
        for (int i = 0; i < M; i++) {
            times[i][0] = in.nextInt();
            times[i][1] = in.nextInt();
            times[i][2] = in.nextInt();
        }
        int start = in.nextInt();
        int end = in.nextInt();

//      Dijkstra算法，邻接矩阵
        int maxValue = 6001;  // 不能用Integer.MAX_VALUE,最大值会出现溢出
        int[][] graph = new int[N + 1][N + 1];  // 邻接矩阵
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                graph[i][j] = (i == j ? 0 : maxValue);
            }
        }
        for(int i = 0; i < times.length; i++){
            int v = times[i][0];
            int w = times[i][1];
            int weight = times[i][2];
            graph[v][w] = weight;
        }
        int[] dist = new int[N + 1];
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        Arrays.fill(dist, maxValue);
        dist[start] = 0;
        queue.add(start);
        while(!queue.isEmpty()){
            int node = queue.poll();
            for(int next = 1; next <= N; next++){
                if(dist[node] + graph[node][next] < dist[next]){
                    dist[next] = dist[node] + graph[node][next];
                    queue.add(next);
                }
            }
        }
        if (dist[end] == maxValue) {
            System.out.println(-1);
        } else {
            System.out.println(dist[end]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

欢迎在评论区指正以及留下自己的更简洁的方法。