C++ || O(mlogn) || Approach Explained || Two solutions - i) Dijkstra ii) Dijkstra + DP
I figured out Solution ii) first and then got to know that only Dijkstra would suffice and got Solution i) after seeing discussions. Both have same time complex
I figured out Solution ii) first and then got to know that only Dijkstra would suffice and got Solution i) after seeing discussions. Both have same time complexity and both passed all test cases.\n\nSolution i)\n\nApproach - Apply Dijkstra from n-1. Suppose waysToReachN1[i] denotes # of ways to reach n-1 from i. Our answer would be waysToReachN1[0].\n\nCases -\ni) i==n-1 | waysToReachN1[i] = 1\nii) If we find better distance for node i from node j then waysToReachN1[i]=waysToReachN1[j]\niii) If we find equal distance for node i from node j then waysToReachN1[i]+=waysToReachN1[j]\n\n```\nclass Solution {\npublic:\n    struct cmp {\n        bool operator()(const vector<long long> &left, const vector<long long> &right){\n          return left[0] >= right[0];\n        }\n    };\n\n    long long dijkstra(int n, vector<vector<vector<long long>>> &adj) {\n        vector<long long> distances(n, LONG_MAX);\n        priority_queue<vector<long long>, vector<vector<long long>>, cmp> Q;\n        distances[n-1] = 0;      \n        vector<long long> waysToReachN1(n, 0);\n        Q.push({distances[n-1], n-1});      \n        waysToReachN1[n-1] = 1;\n        while(!Q.empty()){\n            vector<long long> vec = Q.top(); Q.pop();\n            long long distanceSoFar = vec[0];\n            int node = vec[1];        \n\t\t\tif(distanceSoFar > distances[node]) continue;\n            for(vector<long long> vecNeigh: adj[node]){\n                int node_neigh = vecNeigh[0];\n                long long distanceBetweenTwo = vecNeigh[1];          \n                if(distanceSoFar + distanceBetweenTwo < distances[node_neigh]){\n                    distances[node_neigh] = distanceSoFar + distanceBetweenTwo;\n                    Q.push({distances[node_neigh], node_neigh});        \n                    // found new way\n                    waysToReachN1[node_neigh] = waysToReachN1[node]; \n                } else if(distanceSoFar + distanceBetweenTwo == distances[node_neigh]) {\n                    waysToReachN1[node_neigh]=(waysToReachN1[node_neigh] + waysToReachN1[node])%(1000000007); \n                }\n            }                    \n        }         \n\n        return waysToReachN1[0];            \n    }  \n  \n    int countPaths(int n, vector<vector<int>>& roads) {\n      vector<vector<vector<long long>>> adj(n);\n      for(vector<int> road:roads){\n        long long u = road[0];\n        long long v = road[1];\n        long long time = road[2];\n        adj[u].push_back({v, time});\n        adj[v].push_back({u, time});\n      }\n      \n      return dijkstra(n,adj);      \n    }\n};\n```\nSolution ii)\n```\nclass Solution {\npublic:\n    struct cmp {\n        bool operator()(const vector<long long> &left, const vector<long long> &right){\n          return left[0] >= right[0];\n        }\n    };\n\n    vector<long long> dijkstra(int n, vector<vector<vector<long long>>> &adj) {\n        vector<long long> distances(n, LONG_MAX);\n        priority_queue<vector<long long>, vector<vector<long long>>, cmp> Q;\n        distances[n-1] = 0;      \n        Q.push({distances[n-1], n-1});      \n        while(!Q.empty()){\n            vector<long long> vec = Q.top(); Q.pop();\n            long long distanceSoFar = vec[0];\t\t\t\t\t\t\n            int node = vec[1];        \n\t\t\tif(distanceSoFar > distances[node]) continue;\n            for(vector<long long> vecNeigh: adj[node]){\n                int node_neigh = vecNeigh[0];\n                long long distanceBetweenTwo = vecNeigh[1];          \n                if(distanceSoFar + distanceBetweenTwo < distances[node_neigh]){\n                    distances[node_neigh] = distanceSoFar + distanceBetweenTwo;\n                    Q.push({distances[node_neigh], node_neigh});                         \n                }\n            }                    \n        }\n\n        return distances;            \n    }\n  \n    int countWays(int u, vector<vector<vector<long long>>> &adj, vector<long long> &distances, long long toCoverMore, vector<long long> &dp){\n        int n = adj.size();  \n                            \n        if(dp[u]!=-1) return dp[u];\n      \n        if(u==n-1){            \n            if(toCoverMore == 0) return 1;\n            return 0;\n        }\n      \n        long long res = 0;\n                      \n        for(vector<long long> vecNeigh: adj[u]){\n            int node_neigh = vecNeigh[0];\n            long long distanceBetweenTwo = vecNeigh[1];\n            if(toCoverMore-distanceBetweenTwo == distances[node_neigh]){\n                res=(res + countWays(node_neigh,adj,distances,toCoverMore-distanceBetweenTwo,dp))%(1000000007);                   \n            }                \n        } \n      \n        return dp[u] = res;\n    }\n  \n  \n    int countPaths(int n, vector<vector<int>>& roads) {\n      vector<vector<vector<long long>>> adj(n);\n      for(vector<int> road:roads){\n        long long u = road[0];\n        long long v = road[1];\n        long long time = road[2];\n        adj[u].push_back({v, time});\n        adj[v].push_back({u, time});\n      }\n      \n      vector<long long> distances = dijkstra(n,adj);      \n      vector<long long> dp(n, -1);\n      \n      long long ways = countWays(0, adj, distances, distances[0], dp);      \n      return ways;      \n      \n    }\n};\n```
[]