Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Chocolate Journey problem solution

YASH PAL, 31 July 2024
In this HackerEarth Chocolate Journey problem solution You live in the city B. Your friend is living in the city A. You need a special chocolate xyz. The chocolate is not available in your city and is available only at k cities. There are N cities in the country and M bi-directional roads between the cities and length of each of these bi-directional roads is given. The chocolate is preserved in cold containers and can stay for infinite time if it is preserved in those containers. If it is once taken out of the cold container, It expires in x units of time and you cannot put it back into the cold container to make it available for the infinite time.
HackerEarth Chocolate Journey problem solution

HackerEarth Chocolate Journey problem solution.

#include <array>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <cassert>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <iterator>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

typedef long long ll;

#define eps 1e-9
#define all(a) a.begin(),a.end()
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define sz size()
#define rd(inp) scanf("%lld",&inp)
#define rd2(inp1, inp2) scanf("%lld %lld",&inp1, &inp2)
#define rl(inp) scanf("%d",&inp)
#define pf(out) printf("%lldn", out);

const int mod = (int) 1e9 + 7;
const int linf = 1e9;

ll fpow(ll base,ll power){
ll result = 1;
while (power > 0){
if (power%2 == 1) result=(result*base);
base = (base*base);
power /= 2;
}
return result;
}

struct HASH{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};

#define maxn 101000
int N, M, k, x;
bool isAvaible[maxn];
vector<pair<int, int> > adj[maxn];
int d1[maxn], d2[maxn];

void pre1(){
for( int i = 0 ; i <= N + 1 ; i++ ){
d1[i]=linf;
}
}

void dijkstra1(int node){
pre1();
d1[node] = 0;
priority_queue< pair< int, int > > Q;
Q.push(make_pair(0,node));
while(!Q.empty()){
pair< int, int > top = Q.top();
Q.pop();
int u = top.second;
if(top.first>d1[u]) continue;
for(int i=0;i< adj[u].size();i++){
int to = adj[u][i].F;
int len = adj[u][i].S;
if(d1[u] + len < d1[to]){
d1[to] = d1[u] + len;
Q.push(make_pair(-d1[to],to));
}
}
}
}

void pre2(){
for( int i = 0 ; i <= N + 1 ; i++ ){
d2[i]=linf;
}
}

void dijkstra2(int node){
pre2();
d2[node] = 0;
priority_queue< pair< int, int > > Q;
Q.push(make_pair(0,node));
while(!Q.empty()){
pair< int, int > top = Q.top();
Q.pop();
int u = top.second;
if(top.first>d2[u]) continue;
for(int i=0;i< adj[u].size();i++){
int to = adj[u][i].F;
int len = adj[u][i].S;
if(d2[u] + len < d2[to]){
d2[to] = d2[u] + len;
Q.push(make_pair(-d2[to],to));
}
}
}
}

int cnt[maxn];
unordered_map<pair<int, int>, int, HASH> cntt;
bool vis[maxn];

int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> k >> x;
assert(M <= (N*(N-1))/2 && M <= 1000000);
int i;
for ( i = 1 ; i <= k ; i ++ ){
int theCity;
cin >> theCity;
cnt[theCity] ++;
assert(cnt[theCity] <= 1);
assert(theCity >= 1 && theCity <= N);
isAvaible[theCity] = 1;
}
for ( i = 0 ; i < M ; i ++ ){
int u, v, ld;
cin >> u >> v >> ld;
vis[u] = 1, vis[v] = 1;
cntt[mp(min(u, v), max(u, v))] ++;
assert(u != v);
assert(cntt[mp(min(u, v), max(u, v))] <= 1);
assert(u >= 1 && u <= N && v >= 1 && v <= N);
adj[u].pb(mp(v, ld));
adj[v].pb(mp(u, ld));
}
int A, B;
cin >> A >> B;
assert(A != B);
assert(cnt[B] == 0);
dijkstra1(A);
dijkstra2(B);
if (d1[B] == linf){
cout << -1 << endl;
return 0;
}
vector<int> vertices;
for ( i = 1 ; i <= N ; i ++ ){
if ( vis[i] && d2[i] <= x && isAvaible[i] ){
vertices.push_back(i);
}
}
assert(vertices.size() > 0);
int ans = linf;
for ( i = 0 ; i < vertices.size() ; i ++ ){
ans = min(ans, d1[vertices[i]] + d2[vertices[i]]);
}
cout << ans << endl;
return 0;
}

Second solution

#include<bits/stdc++.h>
#define inf 100000000
#define ll long long
using namespace std;
typedef pair<int,int>ii;
int n,m,k,x;
bool med[100005],vis[100005][2];
vector<ii>v[100005];
int dis[100005][2];
void dijkstra(int s,int type)
{
dis[s][type]=0;
priority_queue<ii,vector<ii>,greater<ii> >pq;
pq.push({0,s});
while(!pq.empty())
{
ii p=pq.top();
int u=p.second,w=p.first;
pq.pop();
if(vis[u][type])continue;
vis[u][type]=1;
for(auto i:v[u])
{
int weight=i.first,ver=i.second;
if(dis[ver][type]>dis[u][type]+weight)
{
dis[ver][type]=dis[u][type]+weight;
pq.push({dis[ver][type],ver});
}
}
}
}
int main()
{
cin>>n>>m>>k>>x;
assert(n>=1 & n<=1e5);
assert(m>=1 && m<=min(1000000LL,(ll)n*(ll)(n-1)/2LL)); //doubt, multiple edges , self loops, cycles
assert(k>=1 && k<=n-1); //doubt
assert(x>=1 && x<=n); //doubt
for(int i=0;i<k;i++)
{
int temp;
cin>>temp;
assert(temp>=1 && temp<=n); //doubt
med[temp]=1;
}
for(int i=1;i<=m;i++)
{
int x,y,w;
cin>>x>>y>>w;
assert(x>=1 && x<=n);
assert(y>=1 && y<=n);
assert(w>=1 && w<=500);
v[x].push_back({w,y});
v[y].push_back({w,x});
}
int a,b;
cin>>a>>b;
assert(a>=1 && a<=n);
assert(b>=1 && b<=n);
assert(med[b]==0);
for(int i=1;i<=100000;i++)for(int j=0;j<2;j++)dis[i][j]=inf;
dijkstra(a,0);
dijkstra(b,1);int ans=100000000;
for(int i=1;i<=n;i++)
{
if(med[i] && dis[i][1]<=x)
{
if(dis[i][1]!=inf && dis[i][0]!=inf && ans>dis[i][1]+dis[i][0])
ans=dis[i][1]+dis[i][0];
}
}
if(ans==100000000)cout<<"-1n";
else cout<<ans<<"n";
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes