lintcode 1565 · Modern Ludo I (spfa, dijkstra)

time: O(VE)

space: O(V)

public class Solution {
    class Pair {
        int node;
        int dist;
        Pair (int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }
    public int modernLudo(int length, int[][] connections) {
        Map<Integer, Set<Integer>> graph = buildGraph(length, connections);
        Queue<Pair> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        pq.offer(new Pair(1, 0));// start from 1, dist:0

        Map<Integer, Integer> res = new HashMap<>();// node point, dist
        for (int i = 1; i <= length; i++) {
            res.put(i, Integer.MAX_VALUE);
        }
        res.put(1, 0);// start from 1, dist:0

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            int curNode = cur.node;
            int curDist = cur.dist;
            for (int nextNode : graph.get(curNode)) {
                if (res.get(nextNode) > curDist) {
                    res.put(nextNode, curDist);
                    pq.add(new Pair(nextNode, curDist));
                }
            }
            int limit = Math.min(curNode+7, length+1);
            for (int nextNode = curNode+1; nextNode < limit; nextNode++) {
                if (res.get(nextNode) > curDist+1) {
                    res.put(nextNode, curDist+1);
                    pq.add(new Pair(nextNode, curDist+1));
                }
            }
        }
        return res.get(length);
    }

    private Map<Integer, Set<Integer>> buildGraph(int length, int[][] connections) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= length; i++) {
            graph.put(i, new HashSet<>());
        }
        for (int i = 0; i < connections.length; i++) {
            int from = connections[i][0];
            int to = connections[i][1];
            graph.get(from).add(to);
        }
        return graph;
    }
}