Create 1976.Number-of-Ways-to-Arrive-at-Destination.cpp

wisdompeak · web-flow · commit 97dd6a1b494c · 2021-08-21T17:25:21.000-07:00
diff --git a/BFS/1976.Number-of-Ways-to-Arrive-at-Destination/1976.Number-of-Ways-to-Arrive-at-Destination.cpp b/BFS/1976.Number-of-Ways-to-Arrive-at-Destination/1976.Number-of-Ways-to-Arrive-at-Destination.cpp
@@ -0,0 +1,64 @@
+using LL = long long;
+using PII = pair<LL,LL>;
+
+class Solution {
+    vector<vector<LL>>adj[201];
+    unordered_map<int,LL> Map[201];
+    long M = 1e9+7;
+    LL dist[201];
+public:
+    int countPaths(int n, vector<vector<int>>& roads) 
+    {        
+        for (auto road: roads)
+        {
+            LL u = road[0], v = road[1], len = road[2];
+            adj[u].push_back({v, len});
+            adj[v].push_back({u, len});
+        }
+        
+        for (int i=0; i<n; i++)
+            dist[i] = -1;
+        
+        priority_queue<PII, vector<PII>, greater<>>pq;
+        pq.push({0,0});
+        
+        while (!pq.empty())
+        {
+            auto [d, c] = pq.top();
+            pq.pop();
+            if (dist[c]!=-1)
+                continue;
+            if (dist[c]==-1)
+                dist[c] = d;
+            
+            for (auto x: adj[c])
+            {                
+                LL nxt = x[0], len = x[1];
+                if (dist[nxt]!=-1) continue;
+                pq.push({d+len, nxt});
+            }            
+        }
+                
+        return dfs(n-1, dist[n-1]);;
+    }
+    
+    LL dfs(int cur, long d)
+    {        
+        if (d != dist[cur])
+            return 0;
+        if (cur==0) return 1;
+        if (Map[cur].find(d)!=Map[cur].end())
+            return Map[cur][d];
+        
+        LL count = 0;
+        for (auto x: adj[cur])
+        {
+            LL nxt = x[0], len = x[1];
+            count += dfs(nxt, d-len);
+            count %= M;
+        }
+        Map[cur][d] = count;
+        return count;
+    }
+    
+};
