HackerEarth Monk in the Secret Services problem solution

In this HackerEarth Monk in the Secret Services problem solution The secret services of Armin, an otherwise peace-loving country, have decided to perform a surgical strike in the war-torn city of Tashka. Tashka is under enemy control and the objective of the strike is to gain control over the city.

The mission is subdivided into the following steps:

1) Divide in groups and infiltrate all enemy bases in Tashka as unarmed civilians, and find the status of enemy's defense strength at that base.

( You can assume that the number of groups are sufficiently large to cover each base separately )

2) Pick up the required amount of ammunition from our secret ammunition store in the city.

3) Return to the bases and destroy the enemy defense.

4) Rush to the Town Hall for the Helicopter pick up out of the town.

There are a total of N buildings in Tashka, numbered from 1 to N . The agents will be dropped at building denoted by S, post which they will divide into groups and each enemy base will have a group moving towards it. The ammunition store is denoted by A and town hall is denoted by H . All the buildings except these three are enemy bases and are to be infiltrated. There are a total of M bidirectional roads in the city, each road connects two cities. There can be multiple roads between a pair of cities and each road has a time taken to cross associated with its terrain.

Monk is made in charge of the pickup. He can not land the Helicopter before all the groups have arrived at the Town Hall. Find the Minimum units of Time, post dropping the agents, that the Helicopter should be landed such that all groups are able to reach the Town Hall.

HackerEarth Monk in the Secret Services problem solution.

#include<bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define gc getchar_unlocked

int lim=1000000000;
int main()
{
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    int t;
    cin>>t;
    assert(1<=t && t<=10);
    while(t--)
    {
        int i,j,k,n,m,x,c,y;
        cin>>n>>m;
        assert(1<=n && n<=100);
        assert(1<=m && m<=100000);
        int adj[101][101];
        rep(i,n+1)
        {
            rep(j,n+1)
            {
              adj[i][j]=lim;
            }
            adj[i][i]=0;
        }  
        rep(i,m)
        {
            cin>>x>>y>>c;
            assert(1<=x && x<=n);
            assert(1<=y && y<=n);
            assert(1<=c && c<=100);
            adj[x][y]=min(adj[x][y],c);
            adj[y][x]=adj[x][y];
        }
        int s,h,a,ans=0;
        cin>>s>>a>>h;
        for(i=1;i<=n;i++)
        {
          for(j=1;j<=n;j++)
          {
            for(k=1;k<=n;k++)
            {
              adj[j][k]=min(adj[j][i]+adj[i][k],adj[j][k]);
            }
          }
        }

        for(i=1;i<=n;i++)
        {
          if(i==s || i==a || i==h)continue;
          if(adj[s][i]==lim || adj[i][a]==lim || adj[i][h]==lim)
            assert(0);
          ans=max( adj[s][i]+ 2*adj[i][a] + adj[i][h],ans);
        }
        cout<<ans;
        if(t>0)cout<<"\n";
   }
   return 0;
}  

Second solution

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int>   II;
typedef vector< II >      VII;
typedef vector<int>     VI;
typedef vector< VI >  VVI;
typedef long long int   LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))

#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

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

const int INF=int(1e7);
const int N=100;
int dist[N][N];
int main()
{
  fast_io;
  int t;cin>>t;
  while(t--)
  {
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        dist[i][j]=INF;
    for(int i=0;i<n;i++)
      dist[i][i]=0;
    for(int i=0;i<m;i++)
    {
      int x,y,c;
      cin>>x>>y>>c;
      x--,y--;
      if(dist[x][y]>c)
      {
        dist[x][y]=c;
        dist[y][x]=c;
      }
    }
    int s,a,h;
    cin>>s>>a>>h;
    s--,a--,h--;

    //floyd warshall to compute all pairs shortest paths
    for(int k=0;k<n;k++)
      for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
          dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    int ans=0;
    for(int i=0;i<n;i++)
    {
      if(i==s||i==a||i==h)
        continue;
      ans=max(ans,dist[s][i]+dist[i][a]+dist[a][i]+dist[i][h]);
    }
    cout<<ans<<"\n";
  }
  return 0;
}