You are not logged in. Please login at www.codechef.com 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! https://www.codechef.com/problems/REN2013G

asked 14 Apr, 12:23

shivam2197's gravatar image

1★shivam2197
11
accept rate: 0%

converted to question 14 Apr, 18:47

vijju123's gravatar image

6★vijju123 ♦
14.5k11854


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.

link

answered 15 Apr, 02:20

c0deb0t's gravatar image

4★c0deb0t
414
accept rate: 0%

edited 15 Apr, 02:22

Thank You so much @codebot

(15 Apr, 21:14) shivam21971★

No problem!

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

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,540
×1,019
×62

question asked: 14 Apr, 12:23

question was seen: 173 times

last updated: 16 Apr, 00:32