Description

You are resident of some hilly area. Your home is in low height compared to your office. Between your home and office there are number of roads and intersection of roads. Few roads are upwards/downwards (have some slope) and few roads are flat. Slope from locality X to locality Y is defined as Y – X (X indicates no of characters in X, positive slope indicates upward direction and negative slope is downward and 0 slope is flat road ). A locality named X will be attached with another locality named Y if


Slope is 0



Slope is +1/1 and number of common character between X and Y is at least 1



Slope is +2/2 and number of common character between X and Y is at least 2

Distance between locality X and Y is defined as D_{xy} = . For example
X=Bhutan and Y=Nepal = (NB) + (he) + (up) +(ta)+(la)+(n0) During morning when you go to office from home, you want to take a road which is strictly upward and shortest among such roads (consider only distance not slope). Write an efficient C program to find such road. You can randomly select your home and office from following localities and either find shortest path which is strictly upward from home to office or output that there is no such path exists.
Think carefully for efficiency of your program.

Example set of locality: Kullu, Manali, Kumaon, Darjeeling, Sikkim, Nainital,
Shimla,
Mussoorie, Almora, Chamba, Badrinath, Ranikhet, Gulmarg, Dalhousie, Lansdowne, Auli,
Gangtok, Along, Bomdila, Itanagar, Khonsa, Roing, Tawang, Ziro, Haflong, Hamren,
Jatinga, Maibang, Umrangso, Chirmiri, Mainpat, Baijnath, Barog, Chail,
Chitkul,
Churdhar, Dharamkot, Dharamshala, Haripurdhar, Jogindernagar, Kalpa, Kangra, Kasauli, Keylong, Khajjiar, Kiarighat, Kotla, Kufri, Kullu, Manali, Mashobra, Palampur, Rajgarh, Rewalsar, Sangla, Sarahan, Solan, Sundar, Triund
Upload Assignment11A.c

A graph is having n+2 vertices s,t, V_{1}, …V_{n}. There is an edge from V_{x} to V_{y} if 0<yx<=3. Capacity of edge between V_{x} and V_{y} is (x+y). Node s is connected to node V_{x} where 1<=x<=n/4. Edge capacity of an edge between node s and V_{x} is x. There is an edge from V_{x} to node t where x>=3n/4 and x<=n. Consider s as source node and t as sink node in the graph, find the maximum possible flow from s to t with following
constraints:

Flow on an edge doesn’t exceed the given capacity of the edge.

Incoming flow is equal to outgoing flow for every vertex except s and t.
Upload Assignment11B.c