1.can a cracked one installed on alicensed one?
2.can a licensed one installed ona cracked one if it has never been pirated before?

1.YES
2.YES

But my shortest path algorithm still failed....
I first encode the vertice of pirated into 3*i
and the vertice of cracked into 3*i+1,
and the vertice of licensed into 3*i+2,
then construct the graph according to the input, and after that I use a DFS() to take away the edge that comes with a licensed one and is after a pirated one.
Finally I run the SPFA(), is there anything wrong?

I constructed several simple datas to test the DFS() AND SPFA(), it works all right.

hm... I use DP and all work

?? You can have only licensed or pirated vertices; not cracked!

And, btw, singular for "vertices" is "vertex" not "vertice".

Edited by author 01.11.2009 22:23

What is your DP solution? Obviously, we have weighted graph in this problem and we want to know shortest path from one vertex to another. So, it's Dijkstra algorithm, but I'm not sure if you can call it DP... Did you use some special algo?

We need to find shortest path in DAG! So we need not Dijkstra, we need other algo. This algo very same with DP.

Oops, didn't see xi<yi in statement =) Anyway, I used Dijkstra and got AC.

How did you use Dijkstra (N = 10000)?
Did you use heap or priority queue?

O(N^2). It worked even though N=20000 actually(having cracked and licensed vertex for each version). Time was ~0.7 sec.