You are not logged in. Please login at to post your questions!


Please help me approach this question

Can someone explain me how to approach this problem? I am not able to understand the question properly!

asked 14 Apr '18, 12:23

shivam2197's gravatar image

accept rate: 0%

converted to question 14 Apr '18, 18:47

vijju123's gravatar image

4★vijju123 ♦♦

We have a source, which is the castle, and a destination, which is the village, and also some watch towers. We are trying to get from the source to the destination by travelling in straight lines from one location to the next (minimum ammunition used) and we want to find the minimum ammunition used overall from the source to the destination.

To solve this, think of the castle, village, and watch towers as nodes in a graph. From the castle we can directly (straight line) go to each watch tower and the village. From each watch tower we can go to all the other watch towers and the village. Of course, these connections or edges have a weight (or ammunition usage), which is the distance squared (as specified in the problem). So to solve the problem we simply build a graph with all of the connections and nodes and find the shortest path (Dijkstra's algorithm) from the source to the destination.

The time complexity should be around O(n^2) because when building a graph there is a connection between every pair of nodes.


answered 15 Apr '18, 02:20

c0deb0t's gravatar image

accept rate: 0%

edited 15 Apr '18, 02:22

Thank You so much @codebot

(15 Apr '18, 21:14) shivam21971★

No problem!

(16 Apr '18, 00:32) c0deb0t4★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 14 Apr '18, 12:23

question was seen: 201 times

last updated: 16 Apr '18, 00:32