hellcoder's blog

interesting problem
By hellcoder, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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 :).

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

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

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

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.

→ Reply