Problem Name: Band and their concert
Contest Link : ICLFIN05
Algorithm/Technique:
DP
Difficulty Level:
Medium-Hard
Complexity:
O(N^2*T) where N is number of cities and T is maximum time
Explanation:
Since there are two weights on each edge, one of which is used as a constraint and the other is the one to be minimised, a greedy approach like Dijkstra will not work. IN fact the solution involves Dynamic Programming.
So the question arises what should each state represent and where is the optimal substructure. Let our dp have state variables (city, t) where city is the current city and the time is the maximum allowed time to reach city.
Thus dp[c][t] represents minimum toll to reach the city c when maximum allowed time to reach c is t.
Once you know the state variables the recurrence relation is easy to see.
For a given city C,
dp[C][t] = min_over_all_possible_neighbours_to_C( dp[c][t-time[C][c]] + toll[C][c] )
Here c is some city which has an edge with C and is not equal to C.
Here is a snippet for how the dp matrix will be calculated,
#define INF 300000
#define Rep(i, j, n) for(int i = j; i <= n; i++)
//Initialise dp with all elements as INF
Matrix dp(no_cities, VI(max_time + 1, INF));
//Initialising first row
Rep(i, 0, max_time)
dp[0][i] = 0;
//Two Dimensional DP where the 2D Matrix is filled in COLUMN MAJOR sense
Rep(t, 1, max_time){
Rep(city, 1, no_cities-1){
Rep(c, 0, no_cities-1){
if(c == city) continue;
if(t >= time[c][city]){
dp[city][t] = min(dp[city][t], dp[c][t-time[c][city]] + toll[c][city]);
}
}
}
}