HackerEarth Monk's Business Day problem solution

In this HackerEarth Monk's Business Day problem solution Monk visits Biksy, the largest trading market in the land. Biksy has traders from all over the world.

There are a total of N items indexed from 1 to N, that are traded in the market by a total of M dealers. Each trader is characterized by three integers, say i, j, C , meaning that the trader will take i'th item from you and give you j'th item and C units of money. A negative value of C signifies that, in order to get j'th item from the trader, you will have to give i'th item and C units of money. Note that there can be multiple dealers who deal with the same pair of items and some crazy dealers might trade the same item as well i.e. (i = j).

Monk visits Biksy having the item number 1. He collects the data of all the traders and wants to know if there is way by which he can become infinity rich if he acts smart! i.e. if there are a series of profits, repeating which, will always increase the number of units of money with him! Help Monk find the answer to this question. Note that Monk can go to any dealer any number of times.

HackerEarth Monk's Business Day 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
 
struct edge
{
  int u,v,c;
};
vector< vector< int> >orig;
vector< edge > ve;
int n,m;
int dist[100004];
int lim=1000000000;
int foo()
{
  int i,j;
  for(i=1;i<=n;i++)dist[i]=lim;
    dist[1]=0;
  for ( i = 0; i <= n-1; i++)
    {
        for ( j = 0; j < m; j++)
        {
            int u = ve[j].u;
            int v = ve[j].v;
            int c = ve[j].c;
     //       cout<<"\n"<<u<<" "<<v<<" "<<c;
            if (dist[u] != lim)
                dist[v] = min(dist[v],dist[u] + c);
        }
    }
    for ( j = 0; j < m; j++)
    {
      int u = ve[j].u;
      int v = ve[j].v;
      int c = ve[j].c;
      if (dist[u] != lim && dist[u] + c < dist[v])
          return 1;
    }
    return 0;
}

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,x,y,c,q;
        cin>>n>>m;
        orig.clear();
        orig.resize(n+1);
        assert(1<=n && n<=100);
        assert(1<=m && m<=1000);
        ve.clear();
        ve.resize(m);
        rep(i,m)
        {
            cin>>x>>y>>c;
            assert(1<=x && x<=n);
            assert(1<=y && y<=n);
            assert(-1000<=c && c<=1000);
            ve[i].u=x;
            ve[i].v=y;
            ve[i].c=-1*c;
        }
        if(foo())
          cout<<"Yes";
        else
          cout<<"No";
        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 T = 10+1;
const int N = 100+1;
const int M = 1000+1;
const int C = 1000 + 1;
const int INF = int(2e9);
int U[M],V[M],W[M];
int dist[N];
bool ok;
int main()
{
  int t;si(t);
  assert(t<T);
  while(t--)
  {
    ok = false;
    int n,m;
    si(n);si(m);
    assert(1<=n && n<N);
    assert(1<=m && m<M);
    for(int i=0;i<m;i++)
    {
      si(U[i]);si(V[i]);si(W[i]);
      W[i]=-W[i];
      assert(1<=U[i] && U[i]<=n);
      assert(1<=V[i] && V[i]<=n);
      assert(abs(W[i])<C);
    }
    for(int i=1;i<=n;i++)
      dist[i]=INF;
    dist[1]=0;
    for(int i=1;i<=n;i++)
      for(int j=0;j<m;j++)
        if(dist[U[j]]+W[j]<dist[V[j]])
          dist[V[j]]=dist[U[j]]+W[j];
    for(int i=0;i<m;i++)
      if(dist[V[i]] < INF/2 && dist[U[i]]+W[i]<dist[V[i]])
        ok = true;
    puts(ok?"Yes":"No");
  }
  return 0;
}