graph algorithms - all pairs shortest path - floyd warshall
This is a double all pairs shortest path problem. As you see in the problem description you are facing two distinct graphs which at most each one has 26 nodes( upper case letters ), one of them is for Manzoor and the other is for Prof. Miguel.
I first construct two graphs and initialize the adjacency matrices to 100000, then read input and finally run floyd warshall one both of them, and find the minimum cost, how? The places which both of them can go, I add the cost for both of them and find the minimum of these.
Don't forget if there are several places with minimum cost, print them in lexicographical order like this.
10 A G N
Be careful about zero costs, the problem has pointed that the costs are non-negative integers, so it can be zero.
My program first got WA because of this test case.
input :
2
Y U B D 0
M U B D 0
B B
output :
0 B D
because first I checked if they are in the same place and separated this test case from the others.
0 B
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Wednesday, August 26, 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...
-
Prime Cryptarithm The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set ...
-
Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing al...
-
Dynamic Programming The problem wants to know in how many ways one can reach destination ( cell[width][height] ) If there were no obstacle...
No comments:
Post a Comment