Back
Close
  • 115

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

You are given an undirected graph with weighted edges, a start and a goal node, and for each node the heuristic value, which is the estimated distance to the end. Your task is to trace a canonical A* execution (see https://en.wikipedia.org/wiki/A*_search_algorithm ) by computing a shortest path from the start to the goal.

We recall that the A* algorithm will rely on three values for each node v:
- the g-value, which is the minimum distance from the start to v;
- the h-value, which is an estimation of the minimum distance from v to the goal and is given by the heuristic provided in input;
- the f-value, which is the sum of the g-value and h-value.

There is always a path between the start and the goal. The given heuristic is admissible and consistent, meaning that the A* algorithm will always find a shortest path from the start to the goal.

When some nodes have the same f-value, the one with the smaller identifier is considered first.
Input
Line 1: 4 space-separated integers:
N - the number of nodes in the graph (nodes are identified by integers from 0 to N-1),
E - the number of edges in the graph,
S - the identifier of the start node,
G - the identifier of the goal node

Line 2: N space-separated integers - estimated distances to the goal (heuristics) for each node from 0 to N-1

Next E lines: three space-separated integers X Y C that indicate the edge between nodes X and Y with the cost C. Notice that, since the graph is undirected, there is also an edge from Y to X with the same cost.
Output
A sequence of lines containing information about the node expanded in each step of the algorithm: the node's identifier, followed by a space, followed by its f-value.
Constraints
0 < N < 100
0 < E < 10000
0 < C < 1000
Example
Input
3 3 0 2
33 11 0
0 1 10
0 2 40
1 2 20
Output
0 33
1 21
2 30

A higher resolution is required to access the IDE