OJ Board

ytz wrote:My BFS solution result in "out of memory" so I change it to use BFS, however I have the same problem as RAV now, it gives out "WA" on about 5.5 seconds after showing running(5) for a while. BTW, anyone know what this "5" means?

Sorry,I mean from BFS to DFS.

My BFS solution result in "out of memory" so I change it to use BFS, however I have the same problem as RAV now, it gives out "WA" on about 5.5 seconds after showing running(5) for a while. BTW, anyone know what this "5" means?

actually i havent solved this problem yet. but i heard something from my friend, if there are several shortest possible answers, choose one with biggest profit. hope it can help.


I guess this is not true. For example in the second test case the sequence yield the biggest profit is 2 4 3 2, which ...

BTW, I think on this problem BFS is much better than DFS. Using DFS you need to search all solution spaces because you never know there's a shorter solution ahead. By BFS you can stop at the first solution you met.

My idea:
The problem is the intertwine of two factors: "shortest path" and "profit".
if a->b->c->a yield 1.5 and a->d->a yield 1.4, all source shortest path will give the first one because it yields more. However according to the problem the later should be the answer.

All source shortest path is ...