2 days ago

Delta 2.9k

Hyderabad

Question 1.

Humans have been destroving nature for a long time now. The course of rivers are changed, forests are destroyed, mountains are cut and buildings are constructed in the hilly areas. As a result, there is an imbalance in nature and it gets difficult for humans when nature takes matters in hand. There is loss of life and property and what not. The recent heavy rains and floods are an example of it. Roads, bridges, buildings and cars washed away in floods. Hundreds of people are injured and are fighting for life, trying to recover from this devastation. To help out the distressed people, N camps have been set up by the NDRF team, the military and the local police. Each camp is assigned an integer from 1 to N (inclusive). These camps are the places where the teams reside, have equipment, necessary things and much more. There are T bidirectional tracks between these camps and any camp is reachable from any camp. The length of the track between two tracks is present along the track and is represented by L. A pair of camps is said to be directly accessible if there is a direct track between the two. Out of these N, there are R relief camps which are big in size to adhere to the injured people.
Doctors are out in the field and providing help as much as possible. The team of doctors have to leave their camp in the morning, visit each relief camp everyday and come back to their own camp in the evening time. The problem is that they are not able to figure out which camp they should reside in, such that they had to travel the minimum distance. The team can reside in any camp except the relief camp. You have to help the team to figure out the optimal camp for them by figuring out the minimum distance they would be covering everyday.

Example:

a) Number of camps, N = 6
b) Number of tracks between camps, T = 7
c) Number of relief camps = 2
d) Relief camps = [4, 6 ]

It is clear that CAMP 3 is the most ideal camp for the team of the doctors. The minimum distance team will travel = 8

Input Format

The first line of input consists of two space-separated integers, N and T, representing the number of camps and the number of tracks respectively.
The second line of input consists of an integer, R, number of relief camps.
The third line of input consists of an R space-separated integers, representing the relief camps.
Next T lines each consists of three space-separated integers, Si, Di, Li, representing the source camp, destination camp and the length of the track between the pair respectively.

Constraints

1<=N <=10000
1<=T <=50000
1 <= L <=10000
1<=R <=6

Output Format
Print the minimum distance that needs to be traveled by the team of doctors.

Sample test case: 

Input 
6 7
2
46
12 2
15 4
235
262
431
568
643

Output
8

Question 2.

Once in a while, there comes movies for which the people go crazy. It is such a crazy time. The two movies - Barbie and Oppenheimer are breaking the records of sales. The ticket prices are really high and even then the shows are going housefull. In fact, cinema houses are scheduling the shows in the midnight and early morning to meet the demand. Looking at the craze, Mr. X has created a game for the fans where they have a chance to win free tickets for the movie of their choice.

Game:
There is a N°M matrix where each cell of the matrix is represented by either F (Flag) or B (Barbie) or O (Oppenheimer).
How To WIN?
A participant will win the game by fetching all the flags in the matrix.

Rules:

1. A participant present at cell (i, i) can move in any of the cells: (i-1, j), (i+1, j). (i, j+1), (i, j-1) i.e., left, right, top and down.
2. If a participant moves to a cell marked with B, he/she will fall in a pit and to get back in the game they will have to pay one coin.
3. If a participant moves to a cell marked with O, there will be a blast and the participant will be eliminated.
4. The cells marked with F consist of the flag. These are the safe places in the matrix and can be visited by the participant without any restriction.
5. To start the game, a participant can choose any cell of his/her choice.

The game can be played in pairs where one person can guide the other to move to a particular cell.
Moreover, to help the participants, the map of the matrix is shown at the start so that they can plan a strategy and win the game.

Olive is really excited about the game and wants to win it to get the free tickets. But her partner, Popeye, has gone to far lands for some important work. Olive is asking you for help to win the game. She is determined to play the game optimally. When the map is shown, she will remember the cells she needs to move to fetch all the flags. She needs your help to determine the minimum number of coins she would need to get back in the game if she falls in the Barbie pit. Help Olive win the game.

Description of the path: (row_number, column_number, character at cell (i, j) where i is the row
number and i is the column number)

Following the path, Olive would fall in the 4 Barbie pits located at cells:

(1,2)
(4, 4)
(5, 4)
(5,5)

To get out of it, she would require 4 coins. This is the most optimal path with minimum number of coins required.

Note: She could have started with cell (6, 5) and tracked back to the cell (1, 1). The path and minimum number of coins remain the same.

Input Format

The first line of input consists of two space-separated integers, N and M, representing the number of rows and columns of the matrix. Next N rows each consist of M characters. The character can be For B or O only.

Constraints
1 <= N, M <=50
1 <= F <=51
A

Output Format

Print the minimum number of coins Olive needs to fetch all the flags and win the game. If it is not possible for Olive to win the game, print -1.

Sample TestCase 1

Input
65
FBFFO
OBBFO
OOBFO
OOBBO
BBBBB
0000F

Output
4