×

 0 Can someone explain me how to approach this problem? I am not able to understand the question properly! https://www.codechef.com/problems/REN2013G asked 14 Apr '18, 12:23 1●1 accept rate: 0% 15.2k●1●18●59

 0 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 4★c0deb0t 41●4 accept rate: 0% Thank You so much @codebot (15 Apr '18, 21:14) No problem! (16 Apr '18, 00:32) c0deb0t4★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,700
×1,056
×74

question asked: 14 Apr '18, 12:23

question was seen: 201 times

last updated: 16 Apr '18, 00:32