I use bfs where a state is defined by node and time. Is my
approach is wrong? please help me.

???

Edited by author 12.09.2005 15:55

Time is integer in 0..1440,
We have about 500^2 edges,
So 1440*500*500 ~ 4*10^8 (it's of course too big time :)
And you think it can get not TLE?

Try to invent faster algorithm.

BFS is possible if you enhance it doing several tricks.
My AC is 0.265 sec, 5421KB, 85 LOC

I think you mean Ford-Bellman with queue. 0.625 AC. But i have many operations with vectors resize. I think this solve can work faster.

Edited by author 30.05.2012 01:53