1766 - Full Tank?

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?abb=1766

[ArthurGPym]

Hola. Estuve pensando el problema con programacion dinamica. El estado seria la ciudad donde estoy y cuanto "fuel" tengo. Hay dos posibilidades, o ir a una nueva ciudad si tengo el suficiente fuel sin costo o permanecer en mi ciudad pero comprando fuel y gastando. Veo todas las posibilidades y el costo minimo lo guardo en una matriz[ciudades][capacidadMaxima]. El problema es que me dice time limit exceeded. Que estoy haciendo mal?

[HaZard]

¿cómo haces la transición entre las ciudades? cómo haces la dp, memoization o dijkstra ???

[ArthurGPym]

Intenté usar dijkstra pero no logro hacerlo funcionar de forma eficiente/correcta.

[isaac]

Creo que seria bueno antes de aplicar el dijkstra, hacer un arbol de expansion minima descartando tanto los caminos que crean ciclos como los que son imposibles de transitar completos. Seria un buen comienzo

[HaZard]

estando parado en un nodo, no puedes tirarte a ver todas las ciudades y para cada una comprobar los k litros de combustible posibles, es más eficiente que si no tienes combustible hagas una arista hacia el mismo nodo con un litro más, claro si mejora el costo

[ArthurGPym]

Gracias. Voy a probar lo que me dicen y ver si me funciona.