C# - O(maxTime * (E + V)) Dynamic Programming
The solution is based on the winner\'s answer.\nThe d[i, j] state is min fee required to reach node i in time j. The minimum value to reach last node is require
The solution is based on the winner\'s answer.\nThe d[i, j] state is min fee required to reach node i in time j. The minimum value to reach last node is required answer.\n\n```csharp\npublic int MinCost(int maxTime, int[][] edges, int[] passingFees)\n{\n\tint n = passingFees.Length;\n\tDictionary<int, List<(int index, int cost)>> graph = new Dictionary<int, List<(int, int)>>();\n\n\tfor (int i = 0; i < n; i++)\n\t{\n\t\tgraph[i] = new List<(int, int)>();\n\t}\n\n\tforeach (var edge in edges)\n\t{\n\t\tint u = edge[0], v = edge[1], c = edge[2];\n\t\tgraph[u].Add((v, c));\n\t\tgraph[v].Add((u, c));\n\t}\n\n\tint result = int.MaxValue;\n\tint[,] d = new int[n, maxTime + 1];\n\n\tfor (int node = 0; node < n; node++)\n\t{\n\t\tfor (int time = 0; time <= maxTime; time++)\n\t\t{\n\t\t\td[node, time] = int.MaxValue;\n\t\t}\n\t}\n\n\td[0, 0] = passingFees[0];\n\n\tfor (int time = 1; time <= maxTime; time++)\n\t{\n\t\tfor (int i = 0; i < n; i++)\n\t\t{\n\t\t\tforeach (var (index, currentTime) in graph[i])\n\t\t\t{\n\t\t\t\tif (time >= currentTime && d[index, time - currentTime] != int.MaxValue)\n\t\t\t\t{\n\t\t\t\t\td[i, time] = Math.Min(d[i, time], d[index, time - currentTime] + passingFees[i]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\tfor (int i = 1; i <= maxTime; i++)\n\t{\n\t\tresult = Math.Min(result, d[n - 1, i]);\n\t}\n\n\treturn result == int.MaxValue ? -1 : result;\n}\n```
['Dynamic Programming']