### saurabh's blog

By saurabh19 months ago, ,

I have been trying this problem http://www.spoj.pl/problems/FPOLICE/. My idea is to modify the single source shortest path problem to 2-D.So instead of using an array to denote the shortest distance I am using a 2-D matrix where state[i][j] indicates the shortest path from the source to the ith node with still having j time left.(The upper limit on left time is denoted by t) Finally I check the last row (state[n-1][j] for all j=t to j=0 ) the minimum cost.If the minimum cost comes out to be INFINITY then there is no way to reach the destination with atleast 0 time remaining.If minimum costs occur for several values of j i pick up the j which is larger.That is the case which yields more remaining time ( i.e. minimum time).For the single source shortest path I started with dijikistra but then switched to bellman-ford for simplicity.(Doesn't looks like o(n^2*t) will be problem)

UPD: Code modified to fix some bugs

``````#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>

#define PR(x) printf(#x"=%d\n",x)
#define REP(i,a) for(int i=0;i<a;i++)
#define PRARR(x,n) for(int i=0;i<n;i++)printf(#x"[%d]=\t%d\n",i,x[i])
const int INF=2<<29;

int costMatr[101][101];
int timeMatr[101][101];
using namespace std;

int main()
{
int n;
int t;
/*Input section */
int tstcase;
scanf("%d",&tstcase);
while(tstcase--){
scanf("%d %d",&n,&t);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&timeMatr[i][j]);
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&costMatr[i][j]);
}

/*End input */

int state[101][251]; //state[i][j] represents cost from source node to ith node with j time remaining
for(int i=1;i<n;i++)
for(int j=0;j<=t;j++)
{

state[i][j]=INF; //initialize all states to infinity

}

for(int i=0;i<=t;i++) state[0][i]=0; //cost to reach 0th node will be 0 regardless of time left
for(int i=1;i<n;i++)
if(t-timeMatr[0][i]>=0) state[i][t-timeMatr[0][i]]=costMatr[0][i]; //initialize state matrix for neighbours of source nodeh

/*DP begin */
for(int k=t;k>=0;k--)

{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j) continue;

if(costMatr[i][j]+state[i][k]<=state[j][k])
{

if(k-timeMatr[i][j]>=0) {
#ifndef ONLINE_JUDGE
printf("Distance to %dth node updated for time %d. previous value at this state=%d",j,k,state[j][k]);
#endif
state[j][k-timeMatr[i][j]]=costMatr[i][j]+state[i][k];
#ifndef ONLINE_JUDGE
printf("New value for this time %d =%d\n",k-timeMatr[i][j],state[j][k]);
#endif
}
}

}
}

/*DP END*/
/*possible answer in state[n-1][t] where t is all possible values of remaining time */

int minCost=INF;
int minTime=t;
for(int k=t;k>=0;k--)
{
if(state[n-1][k]<minCost)
{
minCost=state[n-1][k];
minTime=k;
}
}
if(minCost==INF)
puts("-1");
else
printf("%d %d\n",minCost,t-minTime);
}
}
``````

Kindly suggest some test cases where my algorithm might be failing.I am almost sure my idea of 2-D Dp is correct,just that I am not able to implement it properly.

UPD: Got the bug.TYpo in `if(costMatr[i][j]+state[i][k]<=state[j][k])` should have been `if(costMatr[i][j]+state[i][k]<=state[j][k-timeMatr[i][j]])`

•
• +2
•

 » 19 months ago, # | ← Rev. 2 →   +1 Here is a simple case where the result is 3 3, but your code produces result 9 1: ``````1 4 5 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 9 1 9 9 0 9 1 9 1 0 9 9 9 9 9 ``````
•
 » » 19 months ago, # ^ |   0 I had noticed that and fixed that too..Since no one was responding forgot to update the code.Now my code gives correct o/p for your test case.
•
 » » 3 months ago, # ^ |   0 Can you please explain how the answer of your test case is 3 3 and not 9 1 ?
•
 » » » 3 months ago, # ^ |   +1 We want to pick the path with minimum total risk, and if there are several such paths, pick the one with minimum time.In the test case moving along edges 1->3, 2->4 and 3->2 has risk 1, and all other edges have risk 9, so the optimal path is 1 -> 3 -> 2 -> 4, which has total risk 3 and time 3.
•
 » » » » 3 months ago, # ^ |   0 Thanks a lot @Sisu

 » 3 months ago, # |   0 If you're still facing problems, I'd suggest you have two DPs. The first one computes the minimum risk such that time taken <= maximum Time. Now in the second DP, find out the minimum time such that sum of risks == minimum risk computed from first DP. I did it using this approach.