Simple Case of Directed Steiner Network Problem.

3570 - Routing (acm icpc live archive).
I was amazed how beautiful and simple solution to this problem actually is. I got stuck on this problem, even though at the first sight it seems easy. Then I asked Prof Mikhail Atallah (our spiritual coach) for help and he pointed out this paper, which explains the solution to this problem and even describes an algorithm for a more general case. I was reading this paper during my flight from Indianapolis to Boston and after I understood it, I was excited to do the actual implementation :-) So, I did implement it and got AC from the first attempt.

The problem is reduced to constructing another graph and finding minimum path in it. You have to use Dijkstra's algorithm with priority queue, because number of nodes in the new graph can be up to 10,000.