HackerEarth Saving Ms. W problem solution

In this HackerEarth Saving Ms. W problem solution Ms. W has been abducted by A Sloth Monster. Now, as her boyfriend, its the duty of Mr. S to save her.

To defeat The Slothy Monster, and save Ms. W from becoming a sloth creature, he has to reach at the certain level of fighting skill.

Currently, he is at the X’th level and he has to reach the Y’th level of fighting skill.

There are different transition method available.

If you choose i’th transition method it will take you from Ai level to Bi level with the cost of Zi amount of stamina(Reverse is also true).

And if he is at skill level i, he can eat a certain Devil Fruit specific to that level which will make him sleep for Hi hours and after that make his stamina equal to Ci.

(Note the the stamina level changes to Ci, not added to the current stamina level).

Although, it’s his choice to eat the Fruit or not. He can choose not to eat the fruit and continue with the current stamina level.

Note that there can be different way to go from one skill level to another skill level with different or same cost of sleep.

Now Mr. S want your help to find out minimum time he has to sleep to reach the ultimate skill level and save his girlfriend.

If there is no way to save her, print -1.

Initial stamina level is 0.

HackerEarth Saving Ms. W problem solution.

#include <bits/stdc++.h>
  #define int long long
  #define w cout
  #define e 'n'
  using namespace std;
  const int N = 1e3 + 10;
  int n , m , start , endd;
   
  int a[N] , b[N] , W[N] , t[N] , c[N] , dist[N][N];
   
  vector<pair<int , int > > v[N];
  vector<int> can[N];
   
  void find_path(int i) {
      dist[i][i] = 0;
      set<pair<int , int > > q;
      q.insert({0 , i});
      while(q.size()) {
          int from = (*q.begin()).second , d = (*q.begin()).first;
          q.erase(q.begin());
          for(auto to : v[from]) {
              int dd = d + to.second;
              if(dd < dist[i][to.first]) {
                  q.erase({dist[i][to.first] , to.first});
                  q.insert({dd , to.first});
                  dist[i][to.first] = dd;
              }
          }
      }
  }   
     
  signed main() {
      ios::sync_with_stdio(0); cin.tie(0) ; cout.tie(0);
      cin >> n >> m >> start >> endd;
  
  for(int i = 0 ; i < m ; i ++ ) {
      int x , y , z; cin >> x >> y >> z;
      v[x].push_back({y , z}) , v[y].push_back({x , z});
  }
  for(int i = 1 ; i <= n ; i ++ ) {
      for(int j = 1 ; j <= n ; j ++ ) {
          dist[i][j] = 1e15;
      }
  }
  for(int i = 1 ; i <= n ; i ++ ) {
      cin >> t[i] >> c[i];
      find_path(i);
  }
  int ans[N] ;
  for(int i = 0 ; i <= n ;i ++ ) ans[i] = 1e15;
  set<pair<int , int > > q;
  ans[start] = 0;
  
  q.insert({0 , start});
  while(!q.empty()) {
      int i = (*q.begin()).second , d = (*q.begin()).first;
      q.erase(q.begin());
      for(int j = 1 ; j <= n ;j ++ ) {
          if(dist[i][j] > t[i]) continue;
          int dd = c[i] + d;
          if(dd < ans[j]) {
              q.erase({ans[j] , j});
              ans[j] = dd;
              q.insert({dd , j});
          }
      }
  }
  if(ans[endd] == 1e15) w << -1;
  else
  cout << ans[endd];
  
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e3 + 1;
ll d[maxn][maxn];
int n, m, c[maxn], h[maxn], a, b;
void floyd(){
  for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
      for(int j = 0; j < n; j++)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> a >> b;
  a--, b--;
  if(a == b)
    return cout << 0, 0;
  memset(d, 63, sizeof d);
  for(int i = 0; i < m; i++){
    int v, u, w;
    cin >> v >> u >> w;
    v--, u--;
    d[u][v] = d[v][u] = min<ll>(d[v][u], w);
  }
  for(int i = 0; i < n; i++)
    cin >> c[i] >> h[i];
  floyd();
  // for(int i = 0; i < n; i++)
  //  for(int j = 0; j < n; j++)
  //    cerr << d[i][j] << " n"[j == n - 1];
  // cerr << 'n';
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      d[i][j] = d[i][j] <= c[i] ? h[i] : LLONG_MAX / 2;
  // for(int i = 0; i < n; i++)
  //  for(int j = 0; j < n; j++)
  //    cerr << d[i][j] << " n"[j == n - 1];
  // cerr << 'n';
  floyd();
  // for(int i = 0; i < n; i++)
  //  for(int j = 0; j < n; j++)
  //    cerr << d[i][j] << " n"[j == n - 1];
  cout << (d[a][b] == LLONG_MAX / 2 ? -1 : d[a][b]) << 'n';
}

HackerEarth Saving Ms. W problem solution

HackerEarth Saving Ms. W problem solution.

Second solution

Leave a Reply

Pages

Practice