Dynamic Programming with Limited Edges
IntuitionThe first thought was to resolve the problem using dynamic programming without repetition of used nodes, but here we have the additional problem that t
# Intuition
The first thought was to resolve the problem using dynamic programming without repetition of used nodes, but here we have the additional problem that the node can`t be visited sequentialy, so we have to work with the limitted next nodes.

# Approach
<!-- Describe your approach to solving the problem. -->
To solve the problem we start working with dynamic programming using a multidimendional array to look into each node that can be used as the path in the current time, ex:

At the time "0" only the first node is a possible source (dp[0,0] != int.max), so for each edge (lets imagine [0,2,2]) we update the node in the given time to have the added cost (dp[2,(0+2)]=dp[0,0] + passingFees[2]) if the previous cost is greater, which is int.Max in this case, so we update it.

In this case at time "1" we do not update any node because all nodes in dp[i,1] are int.Max.

At the time "2" we have our updated dp[2,2] that will push our path in to the future ;).

When we reach our max time all the possibilities are handled and the min value (that is not int.max) is our response for the problem.

# Complexity
- Time complexity:
  O(∣E∣+maxTime⋅∣V∣⋅deg(V)) ≈ O(∣E∣+maxTime⋅∣E∣)

Onde deg(V) é o grau médio dos nós (número de arestas conectadas a cada nó).

- Space complexity:
  O(∣E∣+∣V∣⋅maxTime)

# Code
```csharp []
public class Solution {
    public int MinCost(int maxTime, int[][] edges, int[] passingFees) {
        var graph = BuildGraph(edges, passingFees.Length, false);

        // Init dp
        var dp = new int[passingFees.Length, maxTime+1];

        for(int node = 0; node < passingFees.Length; node++)
            for(int time = 0; time <= maxTime; time++)
                dp[node, time] = int.MaxValue;

        dp[0,maxTime] = passingFees[0];

        int result = int.MaxValue;
        // string matrix = "";
        for(var currentTime = maxTime; currentTime > 0; currentTime--){
            for(int currentNode = 0; currentNode < passingFees.Length; currentNode++){
                var currentCost = dp[currentNode, currentTime];
                // matrix += $"{dp[currentNode, currentTime]},";
                if(currentCost == int.MaxValue) continue;

                foreach(var edge in graph[currentNode]){
                    (int next, int time) = edge;
                    var newCost = currentCost + passingFees[next];
                    if(
                        currentTime >= time 
                        && dp[next, currentTime - time] > newCost
                    ){
                        dp[next, currentTime - time] = newCost;
                        if(next == passingFees.Length - 1 && result > newCost){
                            result = newCost;
                        }
                    }
                }
            }
            if(currentTime % 10 == 0) Console.WriteLine($"Esatmos no tempo {currentTime}");
        }

        return result == int.MaxValue ? -1 : result;
    }

    public static IList<(int dest, int time)>[] BuildGraph(int[][] edges, int size, bool directed) {
        var result = Enumerable.Range(0, size).Select(_ => new List<(int, int)>()).ToArray();
        foreach (var edge in edges) {
            result[edge[0]].Add((edge[1], edge[2]));
            if (!directed) result[edge[1]].Add((edge[0], edge[2]));
        }
        return result;
    }
}
```
['C#']