Contest Link: Problem Link Contest
Problem Link: Practice peer section problem link
Author and Editorialist: Prateek Kumar
Problem Title : Sheldon and the mission
PREREQUISITES:
Graph algorithm- Djkstra’s algorithm (Shortest path algorithm for single source to destination) .
PROBLEM:
We are given a coordinate system. Sheldon is standing at (0,0,0,0). The problem is only concerned with the first 2 dimensions. This gives us a plane, a x-y plane.
Sheldon is standing at (0,0). He needs to get to another point on this plane, (x1,y1). He can use n intermediate points on the plane to get to the destination point.
To move S units in this coordinate system, sheldon has to spend S*S Cal of energy.
He wants the energy used to be minimum, to move from (0,0) to (x1,y1).
Your task is to find the path that uses Sheldon’s minimum energy in going from (0,0) to (x1,y1) and then print this energy.
EXPLANATION:
1.Let us form a graph out of the n points, the source (0,0) and the destination (x1,y1).
2. We store this graph having n+2 nodes and some edges in an adjacency matrix.
3. Sheldon can go from any one point to any other point, there is no restriction on that in the problem statement.
4. We form an edge from each point to every other point. The weight of the edge is the square of the distance between these points (because we want S*S[energy] to be minimum not S[ the distance]).
5. For (a,b) to (c,d), the edge weight is (a-c) * (a-c) + (b-d) * (b-d).
6. We can calculate the edge weight from any one point to any other point using brute force as the constraint on number of points is only 1000. Store all these edge weights from one node to any another node as an adjacency matrix.
7. To calculate minimum energy from single source to single destination we use the Dijkstra’s algorithm on the graph stored as adjacency matrix.
POINTS TO NOTE:
- There are many shortest point algorithms that can be implemented on graphs. Like, Floyd–Warshall algorithm, Bellman–Ford algorithm, Dijkstra’s algorithm and a few more.
- Dijkstra’s algorithm helps to find the shortest distance from a single source to a destination.
- Adjacency matrix stores a graph in a 2-D matrix g[][], g[i][j] is the weight of the edge from i to j.