who can give some tests like test 4, pls.

test 4 is first big test n>90000. And another hint with probability. Calculate p[s]=1-p[s]/100. and p[t]=1-p[t]/100. and use the simple algo BFS . Try to calculate the best probability by formula p[qu->nod]=p[min] * qu->cost; where qu->nod the current node, and qu->cost the probability of this node. Dont forget that the answer is 1.-p[t]. The time of this algo is not good - 0,359, but it is very simple. Good luck!!
P.S.qu->cost the same as p[s] and p[t] must be recalculate at the begining like this
fscanf(in, "%d %d %d", &x, &y, &z);    a[x]=new graf(y,1.-z/100.,a[x]); Sorry for my english!!

Edited by author 04.06.2013 13:48