### hossainzarif's blog

By hossainzarif, 7 weeks ago,

problem
I tried this problem with dijkastra using state graph $(city, silver coin)$ . But, I could not get any way without updating through every edge which would obviously result in TLE. Then, I think let's update with two kind of edge.
$1.$ $(city, silver coin)$ to $(city2, silver coin - cost[city][city2])$ where $cost[city][city2]$ is the silver coins needed to go to $city2$ from $city$.
$2.$ $(city, silver coin)$ to $(city, silver coin + c[city])$
And it worked. But, why this works?

• +1

 » 7 weeks ago, # |   +3 But why shouldn't it work? These are exactly the two things you can do at a city: either go to a new city or wait at the counter to get more silver coins.
•  » » 7 weeks ago, # ^ |   0 What? I was dumb enough to get this. Thanks a lot. If you provide some other shortest path problems, that would be really helpful. Thanks in advance.
•  » » » 7 weeks ago, # ^ |   0