HackerEarth Ways problem solution

In this HackerEarth Ways problem solution Amit and his wife Shweta are in Singapore for their honeymoon. Shweta wants to visit every hotel present there. Amit and Shweta are in their hotel and Amit is planning out how can he fulfill Shweta’s wish.

There are N hotels there(they are staying at the hotel No. 1). There are exactly M roads connecting those hotels (It is guaranteed that any hotel can be visited from any other by roads). Each road has its length. Every day the couple visits exactly one unvisited hotel and come back. Amit wants to take the shortest distance to get to any hotel from his hotel(they use the same path to get back to their hotel).

But there is a problem , Singapore government has announced that the tourists have to choose N-1 roads to move in the city i.e Amit has to choose total N-1 roads such that they can visit all the other hotels . Also path taken to reach any other hotel from their hotel should be the shortest. So in how many ways can Amit choose such N-1 roads.

HackerEarth Ways problem solution.

#include <bits/stdc++.h>
 
typedef long long ll;
 
using namespace std;

ll minT = 1;
ll maxT = 10;
ll minN = 1;
ll maxN = 1000;
ll minM = 0;
ll maxM = 1e5;
ll minC = 1;
ll maxC = 1000;

ll mod = 1e9 + 7;
const int max_n = 1100;
ll inf = 1e15;
 
class compare
{
    public:
        bool operator() (const pair<ll, ll> &a, const pair<ll, ll> &b)
        {
            return (a.first > b.first);
        }
};
 
vector<pair<ll, ll> > v[max_n];
 
ll cnt[max_n], minDis[max_n];
 
priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, compare > pq;
 
bool visited[max_n];
 
int main()
{
    ll t, i, j, n, m, ans, chVer, chDis, nextVer, nextDis, a, b, c, siz;
    pair<ll, ll> tempPr;
 
    scanf("%lld", &t);
    assert(t>=minT && t<=maxT);
 
    while(t--)
    {
        scanf("%lld %lld", &n, &m);
        assert(n>=minN && n<=maxN);
        assert(m>=minM && m<=maxM);
 
        for(i=1;i<=n;++i)
        {
            v[i].clear();
            minDis[i] = inf;
            cnt[i] = 0LL;
            visited[i] = false;
        }
 
        for(i=0;i<m;++i)
        {
            scanf("%lld %lld %lld", &a, &b, &c);
            assert(a>=minN && a<=maxN && a<=n);
            assert(b>=minN && b<=maxN && b<=n);
            assert(c>=minC && c<=maxC);
            
 
            v[a].push_back(make_pair(c, b));
            v[b].push_back(make_pair(c, a));
        }
 
        minDis[1] = 0LL;
        pq.push(make_pair(minDis[1], 1LL));
 
        while(!pq.empty())
        {
            tempPr = pq.top();
            pq.pop();
 
            nextDis = tempPr.first;
            nextVer = tempPr.second;
 
            if(nextDis == inf)
                continue;
 
            //printf("nextVer = %lld   nextDis= %lld\n", nextVer, nextDis);
 
            if(nextDis == minDis[nextVer])
            {
                ++cnt[nextVer];
            }
 
            if(visited[nextVer])
                continue;
            visited[nextVer] = true;
 
            siz = v[nextVer].size();
            for(j=0;j<siz;++j)
            {
                chDis = v[nextVer][j].first;
                chVer = v[nextVer][j].second;
 
                if(minDis[nextVer]+chDis <= minDis[chVer])
                {
                    minDis[chVer] = minDis[nextVer]+chDis;
                    pq.push(make_pair(minDis[chVer], chVer));
                }
            }
        }
 
        ans = 1LL;
        for(i=1;i<=n;++i)
        {
            //printf("cnt[%lld] = %lld\n", i, cnt[i]);
            ans = (ans * cnt[i])%mod;
        }
 
        printf("%lld\n", ans);
    }
 
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define pp pair<int,int>
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
int main() 
{
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t;
  cin>>t;
  while(t--) {
    int n,m,u,v,c,i;
    int dist[1002],ans[1002],vis[1002];
    vector<pp>adj[1002];
    memset(dist,mod,sizeof dist);
    memset(ans,0,sizeof ans);
    memset(vis,0,sizeof vis);
    cin>>n>>m;
    while(m--) {
      cin>>u>>v>>c;
      u--;
      v--;
      adj[u].push_back(make_pair(c,v));
      adj[v].push_back(make_pair(c,u));
    }
    dist[0] = 0;
    priority_queue<pp,vector<pp>,greater<pp> >q;
    q.push(make_pair(0,0));
    while(q.size()) {
      pp p = q.top();
      q.pop();
      ans[p.second] += dist[p.second]==p.first;
      if(vis[p.second]) continue;
      vis[p.second] = 1;
      for(i = 0; i < adj[p.second].size(); i++) {
        if(dist[adj[p.second][i].second] >= dist[p.second] + adj[p.second][i].first) {
          dist[adj[p.second][i].second] = dist[p.second] + adj[p.second][i].first;
          q.push(make_pair(dist[adj[p.second][i].second],adj[p.second][i].second));
        }
      }
    }
    ll x = 1;
    for(i = 0; i < n; i++) {
      x = (x*ans[i])%mod;
    }
    cout<<x<<endl;
  }
  return 0;
}