SDE - 1

You are given a weighted, undirected graph with ‘V’ vertices numbered from 1 to ‘V’ and ‘E’ bidirectional edges.

You have to answer ‘Q’ queries. Every query has two integers, ‘u’, ‘v’, representing the vertices. Your task is to print the shortest distance between ‘u’ and ‘v’ and print -1 if there is no path.

For example:

For the given graph, we have to find the shortest distance between vertices 1 and 3. 
The shortest distance between 1 and 3 is 2 (via 1 <-> 2<-> 3). Hence, the answer is 2.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direc­tion ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat can­not enter into those cells and those with value 1 are open.