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