Can someone explain me how to approach this problem? I am not able to understand the question properly!
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.
Thank You so much @codebot
No problem!