SDE - Intern

You have been given an undirected, connected graph of ‘V’ vertices (labelled from 0 to V-1) and ‘E’ edges. Each edge connecting two nodes 'u' and 'v' has a weight denoting the distance between them.

Your task is to find the shortest path distance from the source node 'S' to all the vertices. You have to return a list of integers denoting the shortest distance between each vertex and source vertex 'S'.

Note:

1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.

2. There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.

For Example:

Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6

The source node is node 0.

The shortest distance from node 0 to node 0 is 0.

The shortest distance from node 0 to node 1 is 5. In the above figure, the green path represents this distance. The path goes from node 0->1, giving distance = 5.

The shortest distance from node 0 to node 2 is 8. In the above figure, the pink path represents this distance. The path goes from node 0->2, giving distance = 8.

The shortest distance from node 0 to node 3 is 7. In the above figure, the yellow path represents this distance. The path goes from node 0->1->3, giving distance = 7.

For a given two-dimensional integer array/list of size (N x M), print it in a spiral form. That is, you need to print in the order followed for every iteration:

a. First row(left to right)
b. Last column(top to bottom)
c. Last row(right to left)
d. First column(bottom to top)

 Mind that every element will be printed only once.

Refer to the Image:

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.