nikunjsoni

1928

Jul 12th, 2021
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int minCost(int maxTime, vector<vector<int>>& all_edges, vector<int>& fees) {
  4.         int n = fees.size();
  5.         vector<vector<pair<int,int>>> edges(n);
  6.         for(vector<int> e : all_edges) {
  7.             int a = e[0];
  8.             int b = e[1];
  9.             int len = e[2];
  10.             edges[a].emplace_back(b, len);
  11.             edges[b].emplace_back(a, len);
  12.         }
  13.         const int INF = 1e9 + 5;
  14.         vector<vector<int>> dp(maxTime + 1, vector<int>(n, INF));
  15.         // dp[time][node] -- min fees
  16.         dp[0][0] = fees[0];
  17.         for(int t = 0; t <= maxTime; ++t) {
  18.             for(int a = 0; a < n; ++a) {
  19.                 int me = dp[t][a];
  20.                 if(me >= INF) continue;
  21.                 for(const pair<int,int>& e : edges[a]) {
  22.                     int b = e.first;
  23.                     int t2 = t + e.second;
  24.                     if(t2 <= maxTime) {
  25.                         dp[t2][b] = min(dp[t2][b], me + fees[b]);
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.         int answer = INF;
  31.         for(int t = 0; t <= maxTime; ++t) {
  32.             answer = min(answer, dp[t][n-1]);
  33.         }
  34.         if(answer >= INF) {
  35.             return -1;
  36.         }
  37.         return answer;
  38.     }
  39. };
RAW Paste Data