JAVA SOLUTION USING DIJKSTRA AND DP
The basic idea is to dijkstra algorithm and find the minimum path from 0 to (n - 1). The catch is that while traversing from one node to another if we encounter
The basic idea is to dijkstra algorithm and find the minimum path from 0 to (n - 1). The catch is that while traversing from one node to another if we encounter a node with more distance then we will initialise the number of ways to reach that node. Similarly, if we encounter a node with same distance as of previous count then we will increment the number of ways to reach that node by its count of previous node. In the end, we will return the number of ways to reach the (n - 1)th node. Hope this solution helps.\n```\nclass Solution {\n    class Pair{\n        int node;\n        int dist;\n        Pair(int node , int dist){\n            this.node = node;\n            this.dist = dist;\n        }\n    }\n    public int countPaths(int n, int[][] roads) {\n        int mod = (int)Math.pow(10 , 9) + 7;\n        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();\n        int rows = roads.length;\n        for(int i = 0 ; i < n ; i++)\n            adj.add(new ArrayList<Pair>());\n        for(int i = 0 ; i < rows ; i++){\n            int from = roads[i][0];\n            int to = roads[i][1];\n            int dis = roads[i][2];\n            adj.get(from).add(new Pair(to , dis));\n            adj.get(to).add(new Pair(from , dis));\n        }\n        PriorityQueue<Pair> pq = new PriorityQueue<>((aa , bb) -> aa.dist - bb.dist);\n        pq.add(new Pair(0 , 0));\n        long[] ways = new long[n];\n        ways[0] = 1;\n        int[] dist = new int[n];\n        Arrays.fill(dist , Integer.MAX_VALUE);\n        dist[0] = 0;\n        while(!pq.isEmpty()){\n            Pair p = pq.remove();\n            int node = p.node;\n            int dis = p.dist;\n            for(Pair pa : adj.get(node)){\n                if((dis + pa.dist) < dist[pa.node]){\n                    ways[pa.node] = ways[node];\n                    dist[pa.node] = dis + pa.dist;\n                    pq.add(new Pair(pa.node , dist[pa.node]));\n                }\n                else if((dis + pa.dist) == dist[pa.node]){\n                    ways[pa.node] += ways[node];\n                    ways[pa.node] = ways[pa.node] % mod;\n                }\n            }\n        }\n        return (int)ways[n - 1];\n    }\n}\n```
['Dynamic Programming', 'Java']