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 Dxy = . For example
X=Bhutan and Y=Nepal = (|N|-|B|) + (|h|-|e|) + (|u|-|p|) +(|t|-|a|)+(|l|-|a|)+(|n|-0) 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, V1, …Vn. There is an edge from Vx to Vy if 0<y-x<=3. Capacity of edge between Vx and Vy is (x+y). Node s is connected to node Vx where 1<=x<=n/4. Edge capacity of an edge between node s and Vx is x. There is an edge from Vx 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
