[Spoj] FISHER - Fishmonger

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : FISHER - Fishmonger
Source            : Spoj 
Category          : Graph Theory, Dynamic Programing
Algorithm         : DAG, DP
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define inf               1e9
 
static const int maxn = 50 + 5;
 
struct info
{
       int toll, timee;
       info(int toll = 0, int timee = 0)
       {
              this->toll = toll;
              this->timee = timee;
       }
       inline bool operator != (const info p) const
       {
              return p.toll != toll && p.timee != timee;
       }
};
 
int n, t;
int travelTime[maxn][maxn], toll[maxn][maxn];
info dp[maxn][1000 + 5];
 
info solve(int curCity = 0, int time_left = 0)
{
       if (time_left < 0) return info(inf, inf);
       if (curCity == n-1) return info(0, 0);
       info &ret = dp[curCity][time_left];
       if (ret != info(-1, -1)) return ret;
       info ans = info(inf, inf);
       for (int nextCity = 0; nextCity < n; nextCity++)
       {
              if (nextCity == curCity) continue;
              info go = solve(nextCity, time_left - travelTime[curCity][nextCity]);
              if (go.toll + toll[curCity][nextCity] < ans.toll)
              {
                     ans.toll = go.toll + toll[curCity][nextCity];
                     ans.timee = go.timee + travelTime[curCity][nextCity];
              }
       }
       return ret = ans;
}
 
void init()
{
       for (int i = 0; i < maxn; i++)
       {
              for (int j = 0; j < 1000 + 5; j++)
              {
                     dp[i][j] = info(-1, -1);
              }
       }
}
 
int main()
{
       //freopen("in.txt", "r", stdin);
 
       while (scanf("%d %d", &n, &t) == 2)
       {
              if (n == 0 && t == 0) break;
              for (int i = 0; i < n; i++)
              {
                     for (int j = 0; j < n; j++)
                     {
                            scanf("%d", &travelTime[i][j]);
                     }
              }
              for (int i = 0; i < n; i++)
              {
                     for (int j = 0; j < n; j++)
                     {
                            scanf("%d", &toll[i][j]);
                     }
              }
              init();
              info ans = solve(0, t);
              printf("%d %d\n", ans.toll, ans.timee);
       }
}

[Spoj] FPOLICE - Fool the Police

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : FPOLICE - Fool the Police
Source            : Spoj 
Category          : Graph Theory, Dynamic Programing
Algorithm         : DAG, DP
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll           long long
#define pll          pair <ll, ll>
#define inf          1e17
 
static const int maxn = 200 + 5;
 
int N;
ll T;
ll timeTaken[maxn][maxn], risk[maxn][maxn];
pll dp[maxn][maxn];
bool vis[maxn][maxn];
 
pll solve(int curPoliceStation, ll timeLeft)
{
       if (timeLeft < 0) return {inf, inf};
       if (curPoliceStation == N) return {0, 0};
       pll &ret = dp[curPoliceStation][timeLeft];
       bool &v = vis[curPoliceStation][timeLeft];
       if (v) return ret;
       v = 1;
       ret = {inf, inf};
       for (int nextPoliceStation = 1; nextPoliceStation <= N; nextPoliceStation++)
       {
              if (nextPoliceStation == curPoliceStation) continue;
              pll go = solve(nextPoliceStation, timeLeft - timeTaken[curPoliceStation][nextPoliceStation]);
              if (go.first + risk[curPoliceStation][nextPoliceStation] < ret.first)
              {
                     ret.first = go.first + risk[curPoliceStation][nextPoliceStation];
                     ret.second = go.second + timeTaken[curPoliceStation][nextPoliceStation];
              }
              else if (go.first + risk[curPoliceStation][nextPoliceStation] == ret.first)
              {
                     if (go.second + timeTaken[curPoliceStation][nextPoliceStation] < ret.second)
                            ret.second = go.second + timeTaken[curPoliceStation][nextPoliceStation];
              }
       }
       return ret;
}
 
int main()
{
       //freopen("in.txt", "r", stdin);
 
       int tc;
       scanf("%d", &tc);
       for (int tcase = 1; tcase <= tc; tcase++)
       {
              scanf("%d %lld", &N, &T);
              for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) scanf("%lld", &timeTaken[i][j]);
              for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) scanf("%lld", &risk[i][j]);
              memset(vis, 0, sizeof vis);
              pll ans = solve(1, T);
              if (ans.first == inf) puts("-1");
              else printf("%lld %lld\n", ans.first, ans.second);
       }
}

[Spoj] KFSTB - Help the Commander in Chief

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : KFSTB - Help the Commander in Chief
Source            : Spoj 
Category          : Graph Theory, Dynamic Programing
Algorithm         : DAG, DP
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll          long long
#define mod         1000000007
#define sz(a)       (int)a.size()
#define memo(a, b)   memset(a, b, sizeof a)
 
static const int maxn = 1e4 + 5;
 
inline int read()    { int a; scanf("%d", &a); return a; }
 
vector <int> dag[maxn];
int tnode, tedge;
int src, des;
 
ll dp[maxn];
bool mem[maxn];
 
inline ll countPath(int u)
{
      if (u == des) return 1;
      if (sz(dag[u]) == 0) return 0;
      ll &ret = dp[u];
      bool &mm = mem[u];
      if (mm) return ret;
      mm = 1;
      ret = 0;
      for (int v : dag[u]) ret = (ret + countPath(v)) % mod;
      return ret;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int tc = read();
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            tnode = read();
            tedge = read();
            src = read();
            des = read();
            for (int e = 1; e <= tedge; e++)
            {
                  int u = read();
                  int v = read();
                  dag[u].emplace_back(v);
            }
            memo(mem, 0);
            ll tpath = countPath(src);
            printf("%lld\n", tpath);
            for (int i = 0; i < maxn; i++) dag[i].clear();
      }
}