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?
→ Pay attention
Before contest
Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
3 days
Register now »
Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
3 days
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/23/2026 00:36:44 (g2).
Desktop version, switch to mobile version.
Supported by
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?