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.
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Monday, August 24, 2009
Subscribe to:
Post Comments (Atom)
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...
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se...
-
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
No comments:
Post a Comment