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.

Solving problems between finals :-)

This week is a dead week in our university. There is a policy that restricts professors from giving quizes or midterms during this week. So, instead they just give a lot of homeworks and you are overloaded with deadlines. Some of the homeworks are boring and so, I entertain myself by solving problems in between.
Here are the problems for today:
1004. Sightseeing trip
Given undirected weighted graph, the problem asks to find simple cycle (you can visit vertex only once) with minimum weight . At the beginning it seems you have to consider all possible cycles and choose the one with minimum weight. You can use Dijsktra's algorithm here though. Just try to delete every possible edge and then find minimum path between nodes of the deleted edge. The cost of such cycle is the weight of minimum path + cost_of_deleted_edge. That was enough to get AC.

1014. The Product of Digits
Simple number-theoretic problem. :-) First, realize that if prime factorization of the integer N has any prime that is bigger than 7, then answer is "-1". Otherwise do simple prime factorization and figure out the degrees of 2, 3, 5 and 7. Suppose these numbers are K2, K3, K5 and K7 respectively. Observe that in order to find the smallest integer it has to be as short (in terms of number of digits) as possible. So, we will be constructing our answer from the end in the following way:
first put K3/2 nines in the end and set K3=K3%2,
next put K2/3 eights before nines and set K2=K2%3,
next put K7 sevens before eights,
next if K2>0 and K3>0 put single six before sevens and set K2=K2-1 and K3=K3-1,
next put K5 fives before in the similar way,
next if K2=2 put single four,
next if K3>0 put single three,
finally if K2=1 put single one.
Also need to handle special case when N=0 or N=1.
That's it.