Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя hossainzarif

a shortest path problem
Автор hossainzarif, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить