a bit of dp: SPOJ - FISHER

Problem Statement:
SPOJ - FISHER

Summary:
You want to move from a source to a destination, via several vertices. Depending on which which vertex you are on, the cost of moving from that state to another will be given in cost[i][j] array, and it will take time[i][j] unit time. You want to minimize the cost of getting to source while at the same time still spend at most T unit time.

Solution:
This is the newest DP approach for me! Let S[v][t] be the minimum cost needed to get to vertex v from the source with time less than or equal to t, then we have the following relation:
S[v][t] is the minimum of:
1. S[v][t-1]  (which means we don't use any other additional vertex to get to v)
2. S[i][t-time[i]] + cost[i][v]  (to get to v, we go to vertex i first)
with a base case: S[v][0] = INF for all v != source, and 0 otherwise.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int inf = (int) 1e9;
int t, N;
int cc[53][53], tt[53][53];
int dp[53][1005];

/* DP on TIME (level) wow! since t < 1000
S(v, t) be the minimum cost for reaching v from 0 with time less than or equal to t.
S(v, 0) = INF for all v != 0, OR 0 for v == 0.
S(v, t) = min( S(v, t-1), S(i, t - time[i][v]) + cost[i][v] )
*/

int main(){
    while(cin >> N >> t, N+t!=0){
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                cin >> tt[i][j];
            }
        }
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                cin >> cc[i][j];
            }
        }
        dp[0][0] = 0;
        for(int i=1;i<=N;++i){
            dp[i][0] = inf;
        }
        int lt = -1;
        for(int k=1;k<=t;++k){
            for(int i=0;i<N;++i){
                dp[i][k] = dp[i][k-1];
                for(int j=0;j<N;++j){
                    if(k < tt[j][i]) continue;
                    dp[i][k] = min(dp[i][k], dp[j][k-tt[j][i]] + cc[j][i]);
                }
            }
            if(dp[N-1][k] != dp[N-1][k-1]){
                lt = k;
            }
        }
        cout << dp[N-1][lt] << " " << lt << endl;
    }
    return 0;
}