C# Dijkstra’s with SortedSet + DFS with Memo | O(E*Log(N^2)) time
SortedSet works as a priority queue here. SortedSet.Add method takes Log(N^2) time in our case which leads to O(ELog(N^2)) time complexity overall where E is th
SortedSet works as a priority queue here. SortedSet.Add method takes Log(N^2) time in our case which leads to O(ELog(N^2)) time complexity overall where E is the number of edges and N is the number of nodes\n\n```\npublic class Solution\n{\n    public int CountRestrictedPaths(int n, int[][] edges)\n    {\n        var graph = new Dictionary<int, List<Tuple<int, int>>>();\n        for (int i = 0; i < edges.Length; i++)\n        {\n            AddNodeToGraph(edges[i][0], edges[i][1], edges[i][2], graph);\n            AddNodeToGraph(edges[i][1], edges[i][0], edges[i][2], graph);\n        }\n        \n        var distanceToLastNode = new Dictionary<int, int>();\n        var priorityQueue = new SortedSet<Tuple<int, int>>();\n        priorityQueue.Add(Tuple.Create(0, n));\n        \n        while (priorityQueue.Count > 0 && distanceToLastNode.Count < n)\n        {\n            var min = priorityQueue.Min;\n            var minDist = min.Item1;\n            var minNode = min.Item2;\n            priorityQueue.Remove(min);\n            \n            if (distanceToLastNode.ContainsKey(minNode))\n                continue;\n            \n            distanceToLastNode.Add(minNode, minDist);\n            \n            var nodeDists = graph[minNode];\n            foreach (var nodeDist in nodeDists)\n            {\n                var node = nodeDist.Item1;\n                var dist = nodeDist.Item2;\n                if (!distanceToLastNode.ContainsKey(node))\n                    priorityQueue.Add(Tuple.Create(minDist + dist, node));\n            }\n        }\n        \n        return DFS(1, n, new int?[n + 1], graph, distanceToLastNode);\n    }\n    \n    private void AddNodeToGraph(int nodeFrom, int nodeTo, int dist, Dictionary<int, List<Tuple<int, int>>> graph)\n    {\n        if (!graph.ContainsKey(nodeFrom))\n            graph[nodeFrom] = new List<Tuple<int, int>>();\n        \n        graph[nodeFrom].Add(Tuple.Create(nodeTo, dist));\n    }\n    \n    private int DFS(int currNode, int target, int?[] dp, Dictionary<int, List<Tuple<int, int>>> graph, Dictionary<int, int> distanceToLastNode)\n    {\n        if (dp[currNode].HasValue)\n            return dp[currNode].Value;\n        \n        if (currNode == target)\n            return 1;\n        \n        var result = 0;\n        var nodeDists = graph[currNode];\n        foreach (var nodeDist in nodeDists)\n        {\n            var nextNode = nodeDist.Item1;\n            if (distanceToLastNode[currNode] > distanceToLastNode[nextNode])\n                result = (result + DFS(nextNode, target, dp, graph, distanceToLastNode)) % (int)(1e9 + 7);\n        }\n        dp[currNode] = result;\n        return result;\n    }\n}\n```
['Depth-First Search']