Leetcode 2492. Minimum Score of a Path Between Two Cities

[Woodyiiiiiii]

这道题是道图问题，小心的地方是图结构可能不是连通的，而且求的是1-n所有点中路径距离最短的一条。

一开始我用dfs+回溯法，一直TLE，不得其所。最后发现，DFS函数中我每次都对访问哈希表擦除，这样会出现一种情况，如果图里面有环，我就相当于要重复两遍路径，无疑这样会大大增加时间成本。所以如何在只遍历边一遍的情况下，遍历所有1-n的连通边呢？

答案是对DFS函数进行修改，不需要每次对访问哈希进行擦除(也可以是访问数组)。

DFS:

class Solution {
    int ans = 10001;

    public int minScore(int n, int[][] roads) {
        // convert roads to map
        Map<Integer, List<End>> edges = new HashMap<>();
        for (int[] road : roads) {
            int start = road[0];
            int end = road[1];
            int cost = road[2];
            if (!edges.containsKey(start)) {
                edges.put(start, new ArrayList<>());
            }
            if (!edges.containsKey(end)) {
                edges.put(end, new ArrayList<>());
            }
            edges.get(start).add(new End(end, cost));
            edges.get(end).add(new End(start, cost));
        }

        // DFS to find the minimum score of the path from 1 to n
        dfs(edges, 1, new HashSet<>());

        return ans;
    }

    private void dfs(Map<Integer, List<End>> edges, int cur, Set<Integer> visited) {
        visited.add(cur);

        edges.get(cur).forEach(end -> {
            ans = Math.min(ans, end.distance);
            if (!visited.contains(end.next)) {
                dfs(edges, end.next, visited);
            }
        });
    }
    
    static class End {
        int next;
        
        int distance;
        
        public End(int next, int distance) {
            this.next = next;
            this.distance = distance;
        }
    }
}

BFS:

class Solution {
    public int minScore(int n, int[][] roads) {
        // convert roads to map
        Map<Integer, List<End>> edges = new HashMap<>();
        for (int[] road : roads) {
            int start = road[0];
            int end = road[1];
            int cost = road[2];
            if (!edges.containsKey(start)) {
                edges.put(start, new ArrayList<>());
            }
            if (!edges.containsKey(end)) {
                edges.put(end, new ArrayList<>());
            }
            edges.get(start).add(new End(end, cost));
            edges.get(end).add(new End(start, cost));
        }

        int ans = 10001;
        // BFS to find the minimum score of the path from 1 to n
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        Set<Integer> visited = new HashSet<>();
        visited.add(1);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            List<End> ends = edges.get(cur);
            for (End end : ends) {
                if (visited.add(end.next)) {
                    queue.add(end.next);
                }
                ans = Math.min(ans, end.distance);
            }
        }

        return ans;
    }

    static class End {
        int next;

        int distance;

        public End(int next, int distance) {
            this.next = next;
            this.distance = distance;
        }
    }
}

两者的共同点都是，每个节点都要遍历所有与之相关的边，这是在原来DFS/BFS上的一个小小改动。

---

• https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/description/