## Monday, September 29, 2014

### 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;
}