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

interesting problem
Автор hellcoder, 10 лет назад, перевод, По-русски

Any Idea of how to solve this problem ?? https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=592&page=show_problem&problem=4768

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Do YOU have any ideas about how to solve this problem? You should always write them when you ask a question (if you care about those who will spend time explaining you the solution).

BTW, the problem can be reduced to an ordinary Dijkstra's algorithm. This answer is as detailed as your question :).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    well i tried to use Dijkstra but because the query number is very high it gave TLE

    so it is clearly not useful to mention it, because it was week solution.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      You're lazy to explain even how did you build the graph on which you ran Dijkstra, but still want to others to explain you the complete solution. It's an egoistic behaviour...

      If your solution is correct, but too slow, it can be improved to get AC. And the process of step-by-step improvement will help you to develop your competitive programming skills (and not only them).

      I don't mind to help you, but a teacher's job is not to give the learner the complete solution, but to point the learner to the correct direction. Thank you for your understanding.

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very nice problem indeed!

A little hint: Try to work with edges instead of nodes. That is, compute shortest path that ends in a certain edge instead of a certain node, and make an adjacency list for the edges instead of the nodes.

→ Ответить