Sunday, December 12, 2010

UVA - 11792 - Krochanska is Here!

problem statement

graph search algorithm - single source unweighted shortest path - BFS from some sources

You are facing a multi BFS problem that you have to run BFS from multiple sources, that are called important stations here.
First I have a boolean 2d array "mark" that I can figure out that in each line which stations are used and find out which stations are "important stations".
Important stations are stations that mark is true for that station in more than one line.
Then easily I run BFS for each important station and find the sum of the distances from
the current important station that I've run BFS from to the other important stations and save that in a vector ave, and finally I find the minimum sum of distances from vector ave and print output.
And how I save my graph : I use a vector adj[10001] and try to save each vertex's
neighbours in that.

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