we have to find min cost path in a mtrix from top left to bottom right.

Move allowed -> Right,left,Bottom,Up.

I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 189 |

2 | Errichto | 188 |

3 | tourist | 180 |

4 | Radewoosh | 173 |

5 | vovuh | 166 |

6 | pikmike | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 161 |

9 | rng_58 | 155 |

10 | farmersrice | 153 |

we have to find min cost path in a mtrix from top left to bottom right.

Move allowed -> Right,left,Bottom,Up.

I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/23/2020 21:38:37 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

is cost value always non negative?

If you can move in all four directions, you have a graph with cycles and then you can't use dp.

If the cost values are non negative is it still true that we can't use dp.

Yes. Because what would dp transitions look like? There can be no cycles among them.

That's how I implemented it can it be more efficient. https://ideone.com/tvKC9r

Can anyone tell me what will be the time complexity of my solution ? I am using dijkstra on a matrix (in above soln) ?

Ffs, make a loop over adjacent cells. Don't repeat the same piece of code 4 times.

What is the number of states (vertices of a graph)? What is the number of transitions (edges)? And finally, what is the complexity of Dijkstra?