C++ dijastra + cached dfs 100% time/space
\n/*\n    First, find out the shortest ditance between node x to node n.\n    DFS to find restricted path.\n*/\ntypedef pair<long,int> pii;\nclass Solution {\np
```\n/*\n    First, find out the shortest ditance between node x to node n.\n    DFS to find restricted path.\n*/\ntypedef pair<long,int> pii;\nclass Solution {\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) \n    {\n        vector<vector<pii>> graph(n+1,vector<pii>{});\n        vector<long> dist(n+1,INT_MAX);\n        dist[n]=0;\n        for (auto edge:edges) {\n            graph[edge[0]].push_back({edge[1],edge[2]});\n            graph[edge[1]].push_back({edge[0],edge[2]});\n        }\n        priority_queue<pii,vector<pii>,greater<pii>> pq;\n        pq.push({dist[n],n}); // dist, node\n        while (!pq.empty()) {\n            auto p=pq.top(); pq.pop();\n            int u=p.second;\n            for (pii vp:graph[u]) { //node, weight\n                int v=vp.first, w=vp.second;\n                if (dist[v]>dist[u]+w) {\n                    dist[v]=dist[u]+w;\n                    pq.push({dist[v],v});\n                }\n            }\n        }\n        vector<int> visited(n+1,-1);\n        return dfs(graph,visited,dist,1,n,INT_MAX);\n    }\n    \n    int dfs(vector<vector<pii>> &graph, vector<int> &visited, vector<long> &dist, int u, int n, long prev)\n    {\n        int mod=1e9+7;\n        if (dist[u]>=prev) return 0;\n        else if (visited[u]>=0) return visited[u];\n        else if (u==n) return 1;\n        int ret=0;\n        for (auto vp:graph[u]) {\n            ret=(ret%mod+dfs(graph,visited,dist,vp.first,n,dist[u])%mod)%mod;\n        }\n        visited[u]=ret;\n        return ret;\n    }\n};\n```
[]