Wednesday, August 26, 2009

10171 - Meeting Prof. Miguel - UVA

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

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...