HackerEarth Lost in a city problem solution

In this HackerEarth Lost in a city problem solution A country consists of n cities and m one-way roads. There is a central city with number s. Each city sells a particular sweet (city i sells sweets of value v[i]).

You are required to go to city d. If you are currently in city x, then you can randomly select and move to one of the cities that is directly reachable from x through a single road. You can perform this technique until you reach city d. You must stop once you reach the destination city.

You can buy sweets only once on your way. Determine the highest value p such that you can take home a sweet whose value is at least p independent of the path that you take. Print the value of p for each destination city d from 1 to n.

HackerEarth Lost in a city problem solution.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5,M=1e6;

inline void chk(int a,int l,int r){
  assert(a>=l&&a<=r);
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  int t;cin>>t;
  chk(t,1,3);
  while(t--){
    int n,m,root;cin>>n>>m>>root;
    chk(n,1,N);chk(m,1,2*N);chk(root,1,n);
    vector<int> val(n);--root;
    for(int i=0;i<n;i++)cin>>val[i],chk(val[i],1,M);
    vector<vector<int>> adj(n);
    set<pair<int,int>> seen;
    for(int i=0;i<m;i++){
      int a,b;cin>>a>>b;
      assert(a!=b);chk(a,1,n);chk(b,1,n);
      --a;--b;
      adj[a].push_back(b);
      pair<int,int> p={a,b};
      assert(seen.find(p)==seen.end());
      seen.insert(p);
    }
    vector<int> ans(n,M+1),done(n);
    priority_queue<pair<int,int>> pq;
    pq.push({-val[root],root});
    int got=0;
    while(got<n){
      auto best=pq.top();pq.pop();
      int city=best.second,value=-best.first;
      if(done[city])continue;
      done[city]=1;++got;
      ans[city]=value;
      for(auto j:adj[city]){
        if(max(value,val[j])<ans[j])
          pq.push({-max(value,val[j]),j});
      }
    }
    for(int i=0;i<n;i++)
      chk(ans[i],1,M),cout<<ans[i]<<' ';
    cout<<"n";
  }
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 14;

int t, n, m, s, d[maxn], a[maxn];
bool inq[maxn];
vector<int> g[maxn];
void solve(){
  cin >> n >> m >> s;
  s--;
  for(int i = 0; i < n; i++)
    cin >> a[i];
  while(m--){
    int v, u;
    cin >> v >> u;
    v--, u--;
    g[v].push_back(u);
  }
  d[s] = a[s];
  queue<int> q({s});
  while(q.size()){
    int v = q.front();
    q.pop();
    inq[v] = 0;
    for(auto u : g[v])
      if(d[u] > max(a[u], d[v])){
        d[u] = max(a[u], d[v]);
        if(!inq[u]){
          inq[u] = 1;
          q.push(u);
        }
      }
  }
  for(int i = 0; i < n; i++)
    cout << d[i] << ' ';
  cout << 'n';
}
int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> t;
  while(t--){
    memset(d, 63, sizeof d);
    solve();
    fill(inq, inq + n, 0);
    fill(g, g + n, vector<int> ());
  }
}

coding problems solutions