Monday, August 24, 2009

423 - MPI Maelstram - UVA

graph algorithms - all pairs shortest path - floyd warshall O( n^3)

In a system they want to send a message from a source called station 1 to all other n-1 stations.
What question want is the minimum time to do that, so we have to find the minimum time from station 1 to all other stations and then find the maximum between these minimum times and that's the longest time in which all the other stations have gotten the message.
We don't have to send a message directly because of the expensive costs and so we can use intermediate stations to convey the message from station 1 to station k for example.
'n' is not so large so I used floyd-warshall to do this.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...