图算法(二)-最短路径

743. Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Dijkstra

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        //1.define map to store the other vertics and distance
        Mapint[]>> map = new HashMap();
        for(int[] time:times){
            List<int[]> list = map.getOrDefault(time[0],new ArrayList());
            list.add(new int[]{time[1],time[2]});
            map.put(time[0],list);
        }
        //2.init distance
        int[] distance = new int[n+1];
        boolean[] visited = new boolean[n+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        //3.start from the source
        distance[k]=0;
        while(true){
            int curr = -1;
            for(int i=1;i<=n;i++){
                if(!visited[i]){
                    if(curr==-1 || distance[i]i;
                }
            }
            if(curr==-1) break;
            visited[curr]=true;
            for(int[] other:map.getOrDefault(curr,Arrays.asList())){
                if(distance[other[0]]>distance[curr]+other[1]) distance[other[0]] = distance[curr]+other[1];//relaxation
            }
        }
        int max = 0;
        for(int i=1;i<=n;i++) max = Math.max(max,distance[i]);
        return max==Integer.MAX_VALUE ? -1 : max;//坑点，注意有可能压根不连通时要返回-1
    }
}

Dijkstra PQ 优化版

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        //1.define map to store the other vertics and distance
        Mapint[]>> map = new HashMap();
        for(int[] time:times){
            List<int[]> list = map.getOrDefault(time[0],new ArrayList());
            list.add(new int[]{time[1],time[2]});
            map.put(time[0],list);
        }
        //2.init distance
        int[] distance = new int[n+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y)->x[1]-y[1]);
        //3.start from the source
        distance[k]=0;
        pq.offer(new int[]{k,0});
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            for(int[] other:map.getOrDefault(curr[0],Arrays.asList())){
                if(distance[other[0]]>distance[curr[0]]+other[1]) {
                    distance[other[0]] = distance[curr[0]]+other[1];//relaxation
                    pq.offer(new int[]{other[0],distance[other[0]]});
                }
            }
        }
        int max = 0;
        for(int i=1;i<=n;i++) max = Math.max(max,distance[i]);
        return max==Integer.MAX_VALUE ? -1 : max;//坑点，注意有可能压根不连通时要返回-1
    }
}

787. Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 104
• There will not be any multiple flights between two cities.
• 0 <= src, dst, k < n
• src != dst

BFS 这个解法会超时

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Mapint[]>> map = new HashMap();
        for(int[] flight:flights){
            List<int[]> list = map.getOrDefault(flight[0],new ArrayList());
            list.add(new int[]{flight[1],flight[2]});
            map.put(flight[0],list);
        }
        int min = Integer.MAX_VALUE;
        Queue<int[]> queue = new LinkedList();
        queue.offer(new int[]{src,0});
        //一层一层向外算
        while(!queue.isEmpty() && k>=-1){
            int size = queue.size();
            k--;
            for(int i=0;i){
                int[] curr = queue.poll();
                int node = curr[0];
                int cost = curr[1];
                if(node==dst) min = Math.min(min,cost);
                for(int[] flight:map.getOrDefault( node ,Arrays.asList())){
                    if(cost+flight[1]new int[]{flight[0],cost+flight[1]});//如果遇到处理过的点cost已经比当前还小，那么直接跳过
                }
            }
        }
        return min==Integer.MAX_VALUE ? -1 : min;
    }
}

类似dikjistra pq解法

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Mapint[]>> map = new HashMap();
        for(int[] flight:flights){
            List<int[]> list = map.getOrDefault(flight[0],new ArrayList());
            list.add(new int[]{flight[1],flight[2]});
            map.put(flight[0],list);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y)->x[1]-y[1]);
        Map visited = new HashMap();
        pq.offer(new int[]{src,0,k});
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int node = curr[0];
            int cost = curr[1];
            int step = curr[2];
            if(node==dst) return cost;
            visited.put(node,step);
            if( step>=0){
                for(int[] flight:map.getOrDefault(node,Arrays.asList())){
                    if( !visited.containsKey(flight[0]) || step > visited.get(flight[0]) ){//只要step比之前还少，就可以再次尝试
                        pq.offer(new int[]{flight[0],cost+flight[1],step-1});
                    }
                }
            }
        }
        return -1;
    }
}

505. The Maze II

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).

You may assume that the borders of the maze are all walls (see examples).

 Example 1:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Example 2:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: -1
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: -1

 Constraints:

• m == maze.length
• n == maze[i].length
• 1 <= m, n <= 100
• maze[i][j] is 0 or 1.
• start.length == 2
• destination.length == 2
• 0 <= startrow, destinationrow <= m
• 0 <= startcol, destinationcol <= n
• Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
• The maze contains at least 2 empty spaces.

class Solution {
    class Node{
        int x;
        int y;
        int distance;
        Node(int x,int y,int distance){
            this.x=x;
            this.y=y;
            this.distance=distance;
        }
    }
    private int[][] directions = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        //define pq 
        int m = maze.length,n=maze[0].length;
        //定义heap 用于存放当前到个点距离
        PriorityQueue pq = new PriorityQueue((x,y)->x.distance-y.distance);
        //初始化到各点的距离为maxvalue
        int[][] distance =new int[maze.length][maze[0].length];
        for(int i=0;i)  
            for(int j=0;jInteger.MAX_VALUE;
        //将start点放进去，距离为0
        pq.offer(new Node(start[0],start[1],0));
        distance[start[0]][start[1]] = 0;
        //从start点开始向四周遍历
        while(!pq.isEmpty()){
            Node node = pq.poll();
            for(int[] direct:directions){
                int x = node.x;
                int y = node.y;
                int step=0;
                while(x+direct[0]>=0 && x+direct[0]=0 && y+direct[1]){
                    x+=direct[0];
                    y+=direct[1];
                    step++;
                }
                //如果遇到可以relaxation的，加入队列，并更新distance
                if(distance[x][y]>node.distance+step){
                    pq.offer(new Node(x,y,distance[node.x][node.y]+step));
                    distance[x][y] = distance[node.x][node.y]+step;
                }
            }
        }
        //如果destination不是最大值，那么说明它被访问过，否则返回-1
        return distance[destination[0]][destination[1]]==Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]];
    }
}