Autor da análise: 
gabrielrcp
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1253
Resumo
Temos $n \leq 12$ estações. São dados os horários de partida e chegada de $m \leq 100$ trens. Para cada trem é associada uma probabilidade de cancelamento daquele trem. Supõe-se que os trens sejam cancelados de maneira independente uns dos outros.
É dados ainda uma estação de origem, o horário mais cedo que podemos estar na estação de origem ($t_{\textrm{ori}}$), uma estação de destino e o horário máximo que temos para chegar até ela ($t_{\max}$).
Pede-se para encontrar uma sequência de estações tal que, se tentarmos sempre ir de uma estação à outra nessa sequência, sempre tomando o primeiro trem disponível, teremos a maior probabilidade de chegar ao nosso destino à tempo.
Solução
Antes de atacar o problema original, vamos tomar um outro mais simples. Se tivermos fixado uma sequência $E_0, \ldots , E_n$ de estações, e queremos calcular a probabilidade de irmos de $E_0$ à $E_n$, saindo em $t_{\textrm{ori}}$ e chegando antes de $t_{\max}$.
Isso pode ser resolvido por PD. Chame de $f(i, t)$ a probabilidade de, chegando em $E_i$ no tempo $t$, consigamos chegar ao nosso destino à tempo. A probabilidade procurada será $f(0, t_{\textrm{ori}} - 1)$ (esse $-1$ está aí porque não podemos pegar um trem que saia exatamente no mesmo minuto que chegamos à uma estação de trem, exceto pela primeira).
Os casos de fronteira dessa função são:
(1)Agora fixe $i$ e $t$ que não sejam de fronteira. Chamemos de $T_1, \ldots T_k$ os trens que vão de $E_i$ para $E_{i+1}$ cujos tempo de partida seja estritamente maior que $t$. Ordene essa sequência pelos tempos de partida. Adote $\textrm{prob}(T_j)$ como a probabilidade de $T_j$ ser cancelado e $\textrm{chegada}(T_j)$ como o tempo de chegada de $T_j$ à $E_{i+1}$. Valerá a relação:
(2)Com essas relações conseguimos calcular essa probabilidade em $\mathcal{O} ((n + m) t)$, onde $t$ é o tamanho do intervalo de tempo em que estamos considerando. ($n \leq 12$, $m \leq 100$, $t \leq 1400$). Note que podemos enxugar essa PD se tomarmos apenas os horários que tem algum trem partindo, como o número de trens é no máximo 100, isso diminui a complexidade para $\mathcal{O} ((n +m) m)$. Mas isso não é necessário (eu passei esse problema em $0s$ sem isso).
Bom, agora o que podemos fazer é listar todas as rotas entre as estações de origem e destino e calcular a suas probabilidades, guardando sempre a maior. Você pode diminuir um pouco o número de rotas se você nunca voltar para uma estação que já esteve, e tomar só rotas em que hajam trens que, caso não sejam cancelados, te levem da origem ao destino em tempo.
A complexidade final do algoritmo é $\mathcal O ((n+m) t K)$, onde $K$ é o número de rotas testadas. Eu não sei provar que esse número é pequeno. Mas minha intuição me diz que ele não pode ser muito grande, já que temos poucos trens, e ainda tem o tempo como fator.
Uma última observação, que não deve ser novidade para ninguém aqui, mas vou falar mesmo assim. Os tempos são dados no formato hh:mm, que não é muito fácil de trabalhar. Uma maneira de deixar isso mais tratável é converter o horário para a quantidade de minutos desde o começo do dia, ou seja $60 * h + m$. Com isso você pode trabalhar com os horários como um int normal.
Testes
Entrada
4
3
A 12:00 B 12:15 0.1
A 12:10 B 12:14 0.23
A 12:20 B 12:30 0.456
A 12:00 B 12:30
4
A 12:00 B 12:15 0.1
A 12:05 B 12:13 0.15
B 12:20 C 12:35 0.12
A 12:15 C 12:33 0.4
A 12:00 C 13:00
5
A 12:00 B 13:00 0.2
A 12:30 B 13:30 0.0
B 13:20 C 14:00 0.0
C 14:30 D 17:00 0.0
B 14:30 D 17:00 0.1
A 12:00 D 21:00
5
A 12:00 B 13:00 0.2
A 12:30 B 13:30 0.1
B 13:20 C 14:00 0.001
C 14:30 D 17:00 0.001
B 14:30 D 17:00 0.1
A 12:00 D 21:00
Saída
A B
0.9895
A B C
0.8668
A B D
0.9000
A B D
0.8820
Discuta o problema
Eu pretendo escrever sobre esse problema (se ninguém se antecipar).
Mas essa semana está complicada, acho que só semana que vem.
Ricardo, andei pensando na sua solução, e acho que ela está errada mesmo. Olha os dois ultimos casos de teste, e veja se seu programa dá a resposta certa. Eles são quase iguais, mas no terceiro eu coloquei umas probabilidades zero de cancelamento para que seja mais facil de rastrear na mão.
Não tentei, mas acho que dá pra resolver com Dijkstra esse problema. Você pega o caminho de probabilidade máxima, e quando chegar no destino, verifica se chegou antes da hora que queria chegar. O caminho esperado - de probabilidade máxima - vai ser o primeiro caminho que chegar antes da hora pedida.
Se eu entendi direito a sua ideia, voce vai conseguir a probabilidade de chegar ao destino, assumindo que voce em todo momento tome a decisao otima sobre qual trem pegar.
Mas no problema em questao, voce tem que decidir a ordem das estacoes toda antes de comecar a viagem, entao voce nao tem tanta "liberdade" quanto teria se pudesse escolher a cada momento qual seria a melhor rota.
Entendi, mas acho que não faz diferença. Se tomar o devido cuidado para escolher o caminho e calcular as probabilidades, acho que funciona. Eu ainda não pensei com calma nisso e agora nem lembro exatamente as restrições do problema, mas depois eu olho direito e tento assim.
Talvez a parte mais complicada é que se o trem que o sujeito vai pegar for cancelado, ele fica na estação esperando o próximo que vai para a próxima estação da rota escolhida. Para uma dada rota, existem vários caminhos possíveis que se diferem apenas pelas arestas, você tem que considerar todos esses caminhos, mas o dijkstra vai escolher só um aminho.
Bom, eu tentei fazer uma PD para esse problema, mas ela falha para os 2 casos de teste que o Gabriel postou, porque ela não "sabe" qual a rota será tomada a partir do vertice de destino (eu fixei a origem direta na PD, mas a origem indireta ainda fica livre) entao dá errado….
Nao sei, mas acho que essa soluçao do Gabriel pode ser a única…