[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);
       }
}