HackerEarth Minimizing Path Cost problem solution

In this HackerEarth Minimizing Path Cost problem solution In India, there are many railway stations. There’s no way you could avoid one. So, the protagonist in our problem is given N railway stations and M direct two way connections for these railway stations. Let us say that we connect railway station u and v directly – that is to say, you can go from u to v directly without passing any other station.

You have been hired by the Indian Railways (Congratulations!) to compute the shortest path between two railway stations, so that they can minimize the time taken to travel between those stations. M direct connections will be of the following form: Station1 Station2 D, this means there is a direct connection between Station1 and Station2 and there’s a distance of D Kilometers.

Keep in mind that each train takes 1 minute to travel 1 km. The stoppage time is too small, and thus can be ignored.

You will be given Q queries of type Source Destination. You have to find the shortest path from Source to Destination.

HackerEarth Minimizing Path Cost problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll        long long int
#define vi        vector<int>
#define vl        vector<ll>
#define pii       pair<int,int>
#define pil       pair<int, ll>
#define pll       pair<ll, ll>
#define pli       pair<ll, int>
#define pb(v, a)    v.push_back(a)
#define mp(a, b)    make_pair(a, b)
#define MOD       1000000007
#define rep(i, a, b)  for(i=a; i<=b; ++i)
#define rrep(i, a, b) for(i=a; i>=b; --i)
#define si(a)     scanf("%d", &a)
#define sl(a)     scanf("%lld", &a)
#define pi(a)     printf("%d", a)
#define pl(a)     printf("%lld", a)
#define pn        printf("n")
ll pow_mod(ll a, ll b)
{
  ll res = 1;
  while(b)
  {
    if(b & 1)
      res = (res * a) % MOD;
    a = (a * a) % MOD;
    b >>= 1;
  }
  return res;
}
map<string, int> mp;
int main()
{
  int n, m, i, j, k;
  si(n);
  si(m);
  string src, dest;
  ll cst;
  ll dist[n + 1][n + 1];
  rep(i, 1, n)
    rep(j, 1, n)
      dist[i][j] = INT_MAX;
  
  rep(i, 1, n)
  {
    cin>>src;
    mp[src] = i;
  }
  
  rep(i, 0, m - 1)
  {
    cin>>src>>dest>>cst;
    dist[mp[src]][mp[dest]] = cst;
    dist[mp[dest]][mp[src]] = cst;
  }
  rep(i, 1, n)
    dist[i][i] = 0;
  rep(k, 1, n)
    rep(i, 1, n)
      rep(j, 1, n)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  int q;
  si(q);
  while(q--)
  {
    cin>>src>>dest;
    pl(dist[mp[src]][mp[dest]]);
    pn;
  }
  return 0;
}

Second solution

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define repi(i,n) for(int i=0; i<(int)n;i++)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define sortv(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define DRT()  int t; cin>>t; while(t--)
#define TRACE
using namespace std;

//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);


#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;

#define inf 1000000000
int D[100][100];

map<string,int> M;

int main()
{
    int n,m; cin>>n>>m;
    repi(i,n) repi(j,n) D[i][j] = inf; repi(i,n) D[i][i] = 0;
    repi(i,n)
    {
        string s; cin>>s; M[s] = i;
    }
    repi(i,m)
    {
        string s1,s2; int d; cin>>s1>>s2>>d;
        int x = M[s1]; int y = M[s2];
        D[x][y] = d; D[y][x] = d;

    }
    repi(k,n)
        repi(i,n) repi(j,n) D[i][j] = min(D[i][j],D[i][k] + D[k][j]);
    int q; si(q); while(q--)
    {
        string s1,s2; cin>>s1>>s2;
        int x = M[s1]; int y = M[s2];
        cout<<D[x][y]<<endl;
    }
    return 0;

}

coding problems solutions