Ok, consegui passar o problema chicago, mas precisei abandonar a minha idéia original sem saber o que estava dando errado nela. Alguém pode me ajudar?
O que eu fazia era manter uma fila de prioridades de arestas, a prioridade de cada aresta era a probabilidade de atravessar a rua sem ser pego multiplicado pela probabilidade de chegar aonde a aresta começa sem ser pego.
No começo a fila tinha as arestas que saíam do estado inicial e eu iterava até a fila estar vazia. Quando eu chegava em um estado eu verificava se a nova probabilidade era maior do que a que ele já tinha e se fosse eu mudava a sua prioridade e colocava de novo (ou pela primeira vez) as suas arestas na fila.
Para os testes que eu fiz funcionou bem, mas não passava no spoj de jeito nenhum.
Alguém tem alguma idéia a respeito?
Valeu
Eu não entendi direito porque você usa uma fila de prioridades de arestas, e não uma fila de prioridades de vértices. A idéia me parece certa, a única diferença do jeito que eu fiz é essa mesmo. A probabilidade de chegar em um vértice v usando a aresta uv é a probabilidade que eu cheguei em u vezes a probabilidade da aresta uv. Inicialmente, a fila contém o vértice inicial com probabilidade 1.
Talvez seja erro de código mesmo. Se quiser me mandar o código pelo email, posso dar uma olhada depois.
Talvez seja erro de código mesmo. Se quiser me mandar o código pelo email, posso dar uma olhada depois.