ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1934. Black Spot

test 4 WA
Posted by Opportunity 3 Jun 2013 21:31
who can give some tests like test 4, pls.
Re: test 4 WA
Posted by falicos 4 Jun 2013 13:41
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