PKU 3230 Travel

http://poj.org/problem?id=3230
ある旅行者がn個の街をm日間かけて旅行する。このとき、都市iから都市jにいどうするにはコストがかかるが、k日に都市lでは一定の収入が得られる。
旅行者は必ず1からスタートするとき、m日後に最大の所持金はいくらかという問題。

BFSだとTLEしそうだったので、動的計画法に持ち込みました。
dp[都市番号][何日後]=最大の所持金、みたいな感じです。

int cost[100][100];
int income[100][100];
int dp[100][2];

main(){
  int n,m;
  while(cin>>n>>m,n|m){
    rep(i,n)rep(j,n)cin>>cost[i][j];
    rep(i,m)rep(j,n)cin>>income[i][j];
    rep(i,n)dp[i][0]=dp[i][1]=INT_MIN/3;

    dp[0][0]=0;
    int ans=INT_MIN/3;
    rep(i,m){
      rep(j,n){
	rep(k,n){
	  dp[j][i+1&1]=max(dp[j][i+1&1],dp[k][i&1]-cost[k][j]+income[i][j]);
	}
      }
    }
    rep(i,n)ans=max(ans,dp[i][m&1]);
    cout<<ans<<endl;
  }
}