hossainzarif's blog

a shortest path problem
By hossainzarif, 4 years 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

Comments Comments (2)
| Write comment?
»
4 years 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply