## Indeed Interview Question for SDE-2s

- 0of 0 votes

AnswersThere are N stations in a certain region, numbered 1 through N. It takes di,j minutes to travel from Station i to Station j (1 ¥leq i, j ¥leq N)$. Note that di,j=dj,i may not hold.

- neer.1304 August 15, 2019 in United States

You are now at Station 1. From here, you have to visit all the stations exactly once. We assume that you have already visited Station 1. However, due to your schedule, there are M restrictions that must be satisfied. The format of each restriction is as follows:

• Station si must be visited before Station ti. (1≤i≤M)

Find the minimum time required to visit all the stations. Note that the last station to visit can be any of the stations.

Constraints

• 1≤N≤14

• 0≤di,j≤108 (1≤i,j≤N)

• di,i=0 (1≤i≤N)

• 0≤M≤N(N−1)⁄2

• 1≤si,ti≤N (1≤i≤M)

• si≠ti (1≤i≤M)

• There exists a path visiting all the stations under the given restrictions.

Input

Input is given from Standard Input in the following format: N d1,1 … d1,N : dN,1 … dN,N M s1 t1 : sM tM

Output

Print the minimum time required to visit all the stations.

Sample Input 1

4

0 2 3 4

1 0 3 4

1 2 0 4

1 2 3 0

3

1 2

2 3

3 4

Sample Output 1

9

Due to the restrictions, we can only travel as follows: Station 1 → Station 2 → Station 3 → Station 4. Thus, the answer is 2+3+4=9 and we should print 9.

Sample Input 2

3

0 1 20

1 0 20

10 20 0

0

Sample Output 2

21| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm

**Country:**United States

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window