1928

class Solution {
public:
    int minCost(int maxTime, vector<vector<int>>& all_edges, vector<int>& fees) {
        int n = fees.size();
        vector<vector<pair<int,int>>> edges(n);
        for(vector<int> e : all_edges) {
            int a = e[0];
            int b = e[1];
            int len = e[2];
            edges[a].emplace_back(b, len);
            edges[b].emplace_back(a, len);
        }
        const int INF = 1e9 + 5;
        vector<vector<int>> dp(maxTime + 1, vector<int>(n, INF));
        // dp[time][node] -- min fees
        dp[0][0] = fees[0];
        for(int t = 0; t <= maxTime; ++t) {
            for(int a = 0; a < n; ++a) {
                int me = dp[t][a];
                if(me >= INF) continue;
                for(const pair<int,int>& e : edges[a]) {
                    int b = e.first;
                    int t2 = t + e.second;
                    if(t2 <= maxTime) {
                        dp[t2][b] = min(dp[t2][b], me + fees[b]);
                    }
                }
            }
        }
        int answer = INF;
        for(int t = 0; t <= maxTime; ++t) {
            answer = min(answer, dp[t][n-1]);
        }
        if(answer >= INF) {
            return -1;
        }
        return answer;
    }
};