HackerEarth Historic Heist problem solution

In this HackerEarth Historic Heist problem solution Danny Ocean wants to score the biggest heist in history. His target? The MGM Grand. It’s not an easy heist so he wants your help.

The city is in the form of a graph, there are N junctions connected by M bi-directional roads. The time taken to travel on the ith road is ti. The MGM Grand is located at the junction with index s, whereas Danny’s safe house is at junction d. There are several police stations in the city. In the case of any criminal activity, police units are dispatched from all the police stations immediately.

Now Danny wants to know the least amount of time in which he can reach the safehouse after completing the heist from MGM Grand without being intercepted by the police at any junction of the city.

HackerEarth Historic Heist problem solution.

#include <bits/stdc++.h>

using namespace std;

#define s(x) scanf("%d", &x)
#define ll long long int
#define mp make_pair
#define pb push_back
#define INF 100000000000000000LL

int n, m, bad[100005], vis[100005], previous[100005];
vector<int> a[100005];
vector<ll> cost[100005];
ll dist[100005], esc[100005];

int main()
{
    //freopen("Si.txt", "r", stdin);
    //freopen("So.txt", "w", stdout);

    int t, z = 1;
    s(t);

    while (t--) {
        priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
        vector<pair<int, int> > ans;
        int n, m, x, y, i, j, ign, src, dest;
        ll cst;
        cin >> n;

        assert(1 <= n && n <= 100000);

        for (i = 0; i <= n; i++) {
            dist[i] = INF;
            esc[i] = INF;
            previous[i] = -1;
            a[i].clear();
            cost[i].clear();
            vis[i] = 0;
            bad[i] = 0;
        }


        for (i = 1; i <= n; i++) {
            s(x);
            if (x) {
                bad[i] = 1;
                pq.push(mp(0LL, i));
                dist[i] = 0;
                previous[i] = i;
            }
        }

        cin >> src >> dest;

        cin >> m >> ign;
        for (i = 0; i < m; i++) {
            s(x), s(y);
            cin >> cst;

            a[x].pb(y);
            cost[x].pb(cst);
            a[y].pb(x);
            cost[y].pb(cst);
        }

        while (!pq.empty()) {
            pair<ll, int> tt = pq.top();
            pq.pop();
            int cur = tt.second;

            if (vis[cur])
                continue;

            vis[cur] = 1;
            for (i = 0; i < a[cur].size(); i++) {
                if (dist[a[cur][i]] > dist[cur] + cost[cur][i]) {
                    dist[a[cur][i]] = dist[cur] + cost[cur][i];
                    previous[a[cur][i]] = previous[cur];
                    pq.push(mp(dist[a[cur][i]], a[cur][i]));
                }
            }
        }

        /*for (i = 1; i <= n; i++) {
            cout << i << " " << dist[i] << "  " << previous[i] << endl;
        }
        cout << "endn";*/

        while (!pq.empty())
            pq.pop();
        memset(vis, 0, sizeof(vis));

        esc[src] = 0;
        pq.push(mp(0, src));

        while (!pq.empty()) {
            pair<ll, int> tt = pq.top();
            pq.pop();
            int cur = tt.second;

            if (vis[cur])
                continue;


            vis[cur] = 1;
            for (i = 0; i < a[cur].size(); i++) {
                if (esc[a[cur][i]] > esc[cur] + cost[cur][i]) {
                    //cout << cur << " " << a[cur][i] << " "<< dist[a[cur][i]] << endl;
                    if (dist[a[cur][i]] > esc[cur] + cost[cur][i]) {
                        esc[a[cur][i]] = esc[cur] + cost[cur][i];
                        pq.push(mp(esc[a[cur][i]], a[cur][i]));
                    }
                }
            }
        }




        if (esc[dest] == INF)
            cout << "-1n";
        else
            cout << esc[dest] << endl;
    }

    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll vis[100005],dist[100005],n,m,x,y,c,t,s,d,tim[100005];
vector<pair<ll,ll> >v[100005];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >pq;
void init()
{
    ll i;
    for(i=1;i<=n;i++)
    {
        vis[i]=0;
        dist[i]=1e15;
        tim[i]=1e15;
        v[i].clear();
    }
    while(!pq.empty())
    pq.pop();
}
void dijikstra()
{
    ll i,j,k;
    dist[s]=0;
    pq.push({0,s});
    while(!pq.empty())
    {
        j=pq.top().first;//cost
        k=pq.top().second;//parent
        pq.pop();
        if(vis[k])
        continue;
        vis[k]=1;
        for(i=0;i<v[k].size();i++)
        {
            x=v[k][i].first;
            y=v[k][i].second;
            if(dist[y]>x+j&&tim[y]>x+j)
            {
                dist[y]=x+j;
                pq.push({dist[y],y});
            }
        }
    }
}
void dijikstra1()
{
    ll i,j,k;
    while(!pq.empty())
    {
        j=pq.top().first;//cost
        k=pq.top().second;//parent
        pq.pop();
        if(vis[k])
        continue;
        vis[k]=1;
        for(i=0;i<v[k].size();i++)
        {
            x=v[k][i].first;
            y=v[k][i].second;
            if(tim[y]>x+j)
            {
                tim[y]=x+j;
                pq.push({tim[y],y});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,ans;
    cin>>t;
    while(t--)
    {
        cin>>n;
        init();
        vector<ll>police;
        for(i=1;i<=n;i++)
        {
            cin>>j;
            if(j)
            {
                police.push_back(i);
            }
        }
        cin>>s>>d;
        cin>>m>>j;
        for(i=1;i<=m;i++)
        {
            cin>>x>>y>>c;
            v[x].push_back({c,y});
            v[y].push_back({c,x});
        }
        for(i=0;i<police.size();i++)
        {
            tim[police[i]]=0;
            pq.push({0,police[i]});
        }
        dijikstra1();
        while(!pq.empty())
        pq.pop();
        memset(vis,0,sizeof vis);
        dijikstra();
        if(dist[d]>=1e15)
        cout<<"-1n";
        else
        cout<<dist[d]<<"n";
    }
    return 0;
}

HackerEarth Historic Heist problem solution

HackerEarth Historic Heist problem solution.

Second solution

Leave a Reply

Pages

Practice