Description

Submission

class Solution {
    typedef pair<int,int> PII;
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n = passingFees.size();

        vector<vector<PII>> graph(n);
        vector<vector<int>> dp(n+1, vector<int>(maxTime+1, INT_MAX/2));
        dp[0][0] = passingFees[0];
        vector<int> earliestTime(n+1, INT_MAX/2);

        for(auto edge: edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
            graph[edge[1]].push_back({edge[0], edge[2]});
        }

        queue<PII> q;   // id, time
        q.push({0, 0});

        while(!q.empty()) {
            auto [id, t] = q.front();
            q.pop();

            for(auto [newId, dt]: graph[id]) {
                int newT = t + dt;
                int newFee = dp[id][t] + passingFees[newId];
                if(newT > maxTime) continue;
                if(newT > earliestTime[newId] && dp[newId][earliestTime[newId]] < newFee) continue;
                if(newFee < dp[newId][newT]) {
                    dp[newId][newT] = newFee;
                    q.push({newId, newT});
                    earliestTime[newId] = min(earliestTime[newId], newT);
                }
            }
        }

        int ret = INT_MAX/2;
        for(int t = 0; t <= maxTime; ++t) {
            ret = min(ret, dp[n-1][t]);
        }

        if(ret == INT_MAX/2) return -1;
        return ret;
    }
};

// dp[n][t]: the cost to reach node n at time t