Restore Peace

We will iterate over the battle cities in the given order and calculate the distance between the current position of the king and his next position each time separately.

To calculate the distance between two cities, we will use the breadth-first search algorithm.

Algorithm:

• bfs function:
  • This function will take the current city, “cur” and the next city, “tar” of the king, and the graph as arguments and will return the distance between these two cities.
  • Declare two arrays - “vis” and “dist” to store whether a city is visited or not and to store the distance of each city from the “cur” city, respectively.
  • Declare a queue of integers, and push the “cur” city to it.
  • Set the distance of the “cur” city as 0.
  • While ‘q’ is not empty.
    • Take out the front element of the ‘q’.
    • If this is the “tar” city, return the distance of this city from the “dist” array.
    • Iterate over the adjacent cities.
      • If the city is not visited
        • Mark it as visited
        • Push it to the queue
        • Update the “dist” array.

• given function:
  • Create the graph from the given input.
  • Declare two variables - “ans” to store the answer and “cur” to store the current city of the king.
  • Iterate over the battle cities.
    • Declare a visited array “vis”.
    • Calculate the distance between the current city and the next city using the “bfs” function. Add this to the “ans”.
    • Update the “cur” as the next city.
  • Return the “ans”.

O(Q * N), where  ‘N’ and ‘Q’ represent the total number of cities and the number of cities the king has to visit, respectively.

Since we are iterating over the battles array and in each iteration we are calling the “bfs” function, which has a time complexity of O(N), the overall time complexity will be O(Q * N).

O(N), where ‘N’ represents the total number of cities in the kingdom.

Since we are creating a graph and the visited array and queue in the “bfs” function, each having a size of ‘N’, the total time complexity will be O(N).