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.
#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("%lld\n", 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<<"-1\n";
else cout<<ans<<"\n";
return 0;
}
0 Comments