Java algorithm help: Description: After hearing about the epidemic of obesity in

Question

Java algorithm help:

Description:

After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to creating a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distance between this farthest pair of farms.

Input
-The fist line has two numbers: the first number is the total number of farms, and the second number is the total number of of edges (roads between farms).
-Afterward, one line per road: farmA farmB distance direction.

Output
An integer giving the distance between the farthest pair of farms.

Sample Output
52
Hint: The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.

Explanation / Answer

Algorithm for cowmarathon

1.Start the program

2. Declare a variables u,v,w

3. Read the values for u,v and m

4.create the array to read the no of paths

5.Initialize the array for no of paths and read the no of values upto the end

6.create the menthods to calculate the path distances

   add(u,v,w);

   add(u,v,w);

7.initiate the distance using bfs to take max value from farm to another form

8. void bfs(int st)  

    {

    queue<int>q;

    memset(vis,0,sizeof(vis));

    memset(dis,0,sizeof(dis));

    int cur,nex;

    q.push(st);

    vis[st]=1;

    dis[st]=0;

    maxx=0;

    maxx_num=st;

    while(!q.empty())

    {

        cur=q.front();

        q.pop();

        for(int i=head[cur];i!=-1;i=Edge[i].next)

        {

            nex=Edge[i].to;

            if(!vis[nex])

            {

                vis[nex]=1;

                dis[nex]=dis[cur]+Edge[i].w;

                if(maxx<dis[nex])

                {

                    maxx=dis[nex];

                    maxx_num=nex;

                }

                q.push(nex);

            }

        }

    }

}

9.After finding the values sum values according to the path

void add(int f,int t,int w)

{

    Edge[tot].from=f;

    Edge[tot].to=t;

    Edge[tot].w=w;

    Edge[tot].next=head[f];

    head[f]=tot++;

}

10.          F1 --- (13) ---- F6 --- (9) ----- F3

           | |

          (3) |

           | (7)

           F4 --- (20) -------- F2 |

           | |

          (2) F5

           |

           F7

11.From the path add the values ,the above function calculate the distance

The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.  

12. The longest marathon runs from farm 2 via roads

13.displays the result calling the function.

14.end the program

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.