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?
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.
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.