Leetcode 2065. 最大化一张图中的路径价值（DFS / 最短路）

Leetcode 2065. 最大化一张图中的路径价值

暴力DFS

容易想到，从0点出发DFS，期间维护已经走过的距离（时间）和途径点的权值之和，若访问到0点则更新答案，若下一步的距离与已走过的距离和超出了maxTime，则不能向下继续DFS

注意的是，每个点的权值只会计算一次，可以使用一个boolean数组 vis[ ] 来记录该点的权值是否已经计算过
另一种方法是，每当第一次到达一个点并获得权值后，将它的权值修改为0，若后续又一次访问到该点，加0不会影响最终结果，省去vis数组的操作

超时，通过样例59 / 62

class Solution {
    int res;
    public void dfs(int x, int[] values, int[][] map, int maxTime, int time, int sum){
        if(x == 0){
            res = Math.max(res, sum);
        }
        int n = values.length;
        for(int i = 0 ; i < n; i ++){
            if(map[x][i] != 0 && time + map[x][i] <= maxTime){
                int val = values[i];
                values[i] = 0;
                dfs(i, values, map, maxTime, time + map[x][i], sum + val);
                values[i] = val;
            }
        }
        return ;
    }
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        int [][] map = new int [n][n];
        for(int[] e: edges){
            int a = e[0];
            int b = e[1];
            int t = e[2];
            map[a][b] = t;
            map[b][a] = t;
        }
        res = 0;
        int val = values[0];
        values[0] = 0;
        dfs(0, values, map, maxTime, 0, val);
        return res;
    }
}
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

最短路 优化剪枝

注意到，当判断一个点是否可以继续深入时，可以考虑的一种剪枝方式是，向该点前进后，若剩余的时间不足以返回0点，则不必向该点DFS
该问题转换为，判断x点回到0点的距离是否超过maxTime - time，即为0点出发的最短路问题，使用Dijstra算法实现

另一方面，当图中的点较稀疏时，使用邻接矩阵遍历找边会导致时间的浪费，因此选择使用邻接表实现图的存储

class Solution {
    int res;
    public void dfs(int x, int[] values, List<int[]>[] map, int maxTime, int time, int sum, int[] dis){
        if(x == 0){
            res = Math.max(res, sum);
        }
        int n = values.length;
        for(int arr[] : map[x]){
            int y = arr[0];
            int t = arr[1];
            // 求和时增加dis，若不足返回0点则不必DFS
            if(time + t + dis[y] <= maxTime){
                int val = values[y];
                values[y] = 0;
                dfs(y, values, map, maxTime, time + t, sum + val, dis);
                values[y] = val;
            }
        }
        return ;
    }
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        // 邻接表  map[x]为x发出的边的集合List，List中的每个int[]，int[0]为终点，int[1]为距离
        List<int[]>[] map = new ArrayList[n];
        for(int i = 0 ; i < n; i ++){
            map[i] = new ArrayList<int[]>();
        }
        for(int[] e: edges){
            int a = e[0];
            int b = e[1];
            int t = e[2];
            map[a].add(new int[]{b, t});
            map[b].add(new int[]{a, t});
        }
        
        // dijstra
        int inf = Integer.MAX_VALUE;
        int dis[] = new int [n];
        Arrays.fill(dis, inf);
        for(int [] arr: map[0]){
            int y = arr[0];
            int t = arr[1];
            dis[y] = t;
        }
        boolean vis[] = new boolean[n];
        vis[0] = true;
        while(true){
            int min = Integer.MAX_VALUE;
            int index = -1;
            for(int i = 0 ; i < n; i ++){
                if(!vis[i] && dis[i] < min){
                    min = dis[i];
                    index = i;
                }
            }
            if(index == -1)
                break;
            vis[index] = true;
            // 遍历index点发出的边
            for (int[] arr : map[index]) {
                int v = arr[0];
                int t = arr[1];
                if (!vis[v] && dis[index] + t < dis[v]) {
                    dis[v] = dis[index] + t;
                }
            }
        }

        // DFS
        res = 0;
        int val = values[0];
        values[0] = 0;
        dfs(0, values, map, maxTime, 0, val, dis);
        return res;
    }
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76