C++ BFS Dijkastra  🔥🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<pair<long long,long long>>adj[n];\n        \n        for(auto it: roads)\n        {\n            adj[it[0]].push_back({it[1],it[2]});\n            adj[it[1]].push_back({it[0],it[2]});\n        }\n        \n        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>pq;\n    \n        vector<long long> dist(n,LONG_MAX),ways(n,0);\n        dist[0]=0;\n        ways[0]=1;\n        int mod=(1e9 +7);\n        pq.push({0,0});\n        while(!pq.empty())\n        {\n          long long d=pq.top().first;\n          long long int node=pq.top().second;\n          pq.pop();\n          for(auto it:adj[node])\n          {\n              long long adjnode=it.first;\n              long long int edgwt=it.second;\n      //this is the first time i have entered with short distance \n              if((d+edgwt)<dist[adjnode])\n              {\n                  dist[adjnode]=d+edgwt;\n                  ways[adjnode]=ways[node];\n                  pq.push({dist[adjnode],adjnode});\n              } else if((d+edgwt)==dist[adjnode])\n              {\n                   ways[adjnode]=((ways[adjnode]%mod + ways[node])%mod)%mod;\n              }\n          }\n         \n        }\n        return ways[n-1]%mod;\n    }\n};\n```
['Breadth-First Search', 'C++']