HackerEarth Pilgrims and Portals problem solution

In this HackerEarth Pilgrims and Portals problem solution Pritam is a priest in his village. He needs to pay his respects to k shrines which his all ancestors have visited and had asked their successors to pay the respect. But he hates walking so he wants to minimize the distance he has to travel to pay his respects. As he is busy packing he asks you to help him. He has acquired a bunch of portal scrolls through which he can create portal networks. Portals can only be created at shrines , and after entering a portal a he can exit at any desired portal. You have to give the minimum distance Pritam has to travel. There are number of cities which don’t have shrines but that can be traveled through.

You will be given n the number of cities and out of which first k cities have shrines. There is road connecting two cities which will be defined by three integers a, b and c where a and b are the cities and c is the distance between the cities. You have to calculate the minimum distance that need to be walked for this pilgrimage given that there is no restriction on number of portals that can be created but need to be created at shrines. After you have told him the distance he’ll decide whether it’s worth undertaking or not. You can assume that he starts from 1st city.

HackerEarth Pilgrims and Portals problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
struct node
{
  int src,dest;
  ll wght;
};
int par[105],rnk[105];
int Find(int nd)
{
  if(par[nd]!=nd)
    par[nd]=Find(par[nd]);
  return par[nd];
}
void Union(int nd1, int nd2)
{
  int x=Find(nd1);
  int y=Find(nd2);
  if(rnk[x]<rnk[y])
    par[x]=y;
  else if(rnk[x]>rnk[y])
    par[y]=x;
  else
  {
    par[y]=x;
    rnk[x]++;
  }
}
bool compare(node n1, node n2)
{
  return n1.wght<n2.wght;
}
ll kruskal(vector<node> g, int n)
{
  vector<node> mst;
  for(int i=0;i<n;++i)
  {
    par[i]=i;
    rnk[i]=0;
  }
  sort(g.begin(),g.end(),compare);
  int cnt=0,cnt1=0;
  ll ans=0;
  while(cnt!=n-1)
  {
    node ne=g[cnt1++];
    int x=Find(ne.src);
    int y=Find(ne.dest);
    if(x!=y)
    {
      ans+=ne.wght;
      mst.push_back(ne);
      Union(x,y);
      cnt++;
    }
  }
  return ans;
}
ll dis[105][105];
void floydWarshell(vector<node> g, int n)
{
  for(int i=0;i<g.size();++i)
  {
    dis[g[i].src][g[i].dest]=g[i].wght;
    dis[g[i].dest][g[i].src]=g[i].wght;
  }
  for(int k=0;k<n;++k)
  {
    for(int i=0;i<n;++i)
    {
      for(int j=0;j<n;++j)
      {
        if(dis[i][k]+dis[k][j]<dis[i][j])
          dis[i][j]=dis[i][k]+dis[k][j];
      }
    }
  }
}
int main()
{
  int t;
  scanf("%d",&t);
  assert(t>=1 && t<=20);
  while(t--)
  {
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    assert(n>=1 && n<=100);
    assert(m>=1 && m<=(n*(n-1))/2);
    assert(k>=1 && k<=n);
    vector<node> graph;
    node nd;
    for(int i=0;i<m;++i)
    {
      scanf("%d %d %lld",&nd.src,&nd.dest,&nd.wght);
      assert(nd.src>=1 && nd.src<=n);
      assert(nd.dest>=1 && nd.dest<=n);
      assert(nd.wght>=1 && nd.wght<=1000000);
      nd.src--;
      nd.dest--;
      graph.push_back(nd);
    }
    for(int i=0;i<n;++i)
      for(int j=0;j<n;++j)
        dis[i][j]=1000000000000000LL;
    for(int i=0;i<n;++i)
      dis[i][i]=0;
    floydWarshell(graph,n);
    graph.clear();
    for(int i=0;i<k;++i)
    {
      for(int j=i+1;j<k;++j)
      {
        nd.src=i,nd.dest=j,nd.wght=dis[i][j];
        graph.push_back(nd);
      }
    }
    printf("%lldn",kruskal(graph,k));
  }
  return 0;
}

Second solution

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define INF 1000000000000000LL
#define lli long long int
#define pii pair<lli,lli>
#define MX 1002
vector<lli>v[MX],r[MX];
lli vis[MX],dis[MX],n,m,k,x,y,c;
int main()
{
    //freopen("in1.txt","r",stdin);
    //freopen("ou1.txt","w",stdout);
  int t;
  cin>>t;
  while(t--)
  {
    for(int i=0;i<MX;i++) v[i].clear(),r[i].clear();
    memset(vis,0,sizeof(vis));
    for(int i=0;i<MX;i++) dis[i]=INF;
    cin>>n>>m>>k;
    while(m--)
    {
      cin>>x>>y>>c;
      v[x].push_back(y);
      r[x].push_back(c);
      v[y].push_back(x);
      r[y].push_back(c);
    }
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push(pii(0,1));
    dis[1]=0;
    while(!q.empty())
    {
      pii p=q.top();q.pop();
      lli d=p.first;
      lli in=p.second;
      //cout<<"d = "<<d<<" in = "<<in<<"n";
      
      if(dis[in]<d) continue;
      if(in<=k)
      {
        vis[in]=1;
        for(int i=0;i<v[in].size();i++)
        {
          lli u=v[in][i];
          c=r[in][i];
          if(vis[u]==0 && dis[u]>c)
          {
            dis[u]=c;
            q.push(pii(c,u));
          }
        }
      }
      else
      {
        for(int i=0;i<v[in].size();i++)
        {
          lli u=v[in][i];
          c=r[in][i];
          if(vis[u]==0 && dis[u]>dis[in]+c)
          {
            dis[u]=dis[in]+c;
            q.push(pii(dis[u],u));
          }
        }
      }
    }
    lli sum=0;
    for(int i=1;i<=k;i++) sum+=dis[i];
    cout<<sum<<"n";  
  }
  return 0;
}

coding problems solutions