HackerEarth The Parking Slot problem solution

In this HackerEarth The Parking Slot problem solution There is a parking facility which is in the form of a graph having N nodes and M edges. The graph does not have self loops or multiple edges.

Each node represents a parking slot and has a capacity of vehicles it can hold. Each edge (u,v) has a weight w representing we can reach from node u to node v incurring a cost of w units. All parking slots have a parking fee F per vehicle which is same for all slots. There are K identical vehicles entering the parking facility, each vehicle enumerated with a distinct number from 1 to K. The vehicles enter in their natural order, that is, vehicle number 1 enters, then vehicle number 2, then 3 and so on till vehicle number K.

For each vehicle, you have to print the minimum total cost that is incurred on the vehicle owner. Here, total cost includes cost of the path taken to reach the parking slot and parking fee of the slot.

It is guaranteed that you can reach any slot from any other slot.

All vehicles entering the parking facility enter from the parking slot 1.

HackerEarth The Parking Slot problem solution .

#include<bits/stdc++.h>
#define ll long long
#define INF 10000000000000000
using namespace std;
typedef pair<ll,int>ii;
ll n,m,k;
vector<pair<int,ll> >v[100005];
ll c[100005],sum,f,cnt,ans[100005],dis[100005];
bool vis[100005];
set<int>st;
void dijkstra(int src)
{
  for(int i=1;i<=n;i++)dis[i]=INF;
  priority_queue<ii,vector<ii>,greater<ii> >pq;
  dis[src]=0;
  pq.push({0,src});
  while(!pq.empty())
  {
    int u=pq.top().second;
    ll d=pq.top().first;
    if(cnt<k)
    {
      ll i;
      for(i=1;i<=min(c[u],k);i++)ans[cnt+i]=d+f;
      cnt=cnt+i-1;
    }
    pq.pop();
    //cout<<u<<" "<<vis[u]<<"n";
    if(vis[u])continue;
    //cout<<"parent: "<<u<<" ";
    vis[u]=1;//st.insert(u);
    for(auto i:v[u])
    {
      ll w=i.second;int node=i.first;
      //cout<<node<<" ";
      if(dis[node]>dis[u]+w)
      {
        //cout<<node<<" ";
        dis[node]=dis[u]+w;
        pq.push({dis[node],node});
      }
    }
    //cout<<"n";
  }
}
int main()
{
  assert(cin>>n>>m>>f);
  assert(n>=1 && n<=1e5);
  assert(m>=n-1 && m<=n*(n-1)/2 && m<=200000);
  assert(f>=1 && f<=1e5);
  for(int i=1;i<=n;i++)
  {
    assert(cin>>c[i]);
    assert(c[i]>=1 && c[i]<=1e3);
    sum+=c[i];
  }
  set<pair<int,int> >ss;
  while(m--)
  {
    int x,y;ll w;
    assert(cin>>x>>y>>w);
    assert(x>=1 && x<=n);
    assert(y>=1 && y<=n);
    assert(x!=y);
    assert(ss.find({x,y})==ss.end() && ss.find({y,x})==ss.end());
    ss.insert({x,y});
    assert(w>=1 && w<=1e9);
    v[x].push_back({y,w});
    v[y].push_back({x,w});
  }
  /*for(int i=1;i<=n;i++,cout<<"n")
  {
    cout<<i<<" ";
    for(auto j:v[i])
      cout<<j.first<<" ";
  }*/
  assert(cin>>k);
  dijkstra(1);
  //cout<<st.size()<<"n";
  //assert(st.size()==n);
  //for(int i=1;i<=n;i++)assert(vis[i]);
  assert(k>=1 && k<=1e5);
  //cout<<sum<<" "<<k<<"n";
  int index=min((ll)k,sum);
  //cout<<"n";
  for(int i=1;i<=index;i++)
    cout<<ans[i]<<" ";
  for(int i=index+1;i<=k;i++)
    cout<<"-1 ";
  return 0;
}

coding problems solutions