10985  Rings'n'Ropes
Moderator: Board moderators
10985  Rings'n'Ropes
How was the correct solution's time complexity?
now I'm using is O((n^2)*m)
I did it because I thinked it should be close to time limit
now I'm using is O((n^2)*m)
I did it because I thinked it should be close to time limit

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
First hint: you should use floydwarshall to find the distance between each pair of vertices.
Second hint: The question asks to find the number of edges that lies on shortest paths from each pair of vertices. Output the maximum of these.
Third hint: define function f(u,v) that counts the number of edges incident to u that is on some shortest path between u and v. Find a recurrence to compute f(u,v) for all u,v in O(n^3) time.
Fourth hint: figure out how to find the answers from the function f
Second hint: The question asks to find the number of edges that lies on shortest paths from each pair of vertices. Output the maximum of these.
Third hint: define function f(u,v) that counts the number of edges incident to u that is on some shortest path between u and v. Find a recurrence to compute f(u,v) for all u,v in O(n^3) time.
Fourth hint: figure out how to find the answers from the function f