hossainzarif's blog

By hossainzarif, 7 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.