Page 1 of 1

1766 - Full Tank?

Posted: Mon Mar 26, 2012 4:16 pm
by ymondelo20

Re: 1766 - Full Tank?

Posted: Sun Aug 14, 2016 10:24 pm
by 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?

Re: 1766 - Full Tank?

Posted: Tue Aug 23, 2016 2:19 pm
by HaZard
¿cómo haces la transición entre las ciudades? cómo haces la dp, memoization o dijkstra ???

Re: 1766 - Full Tank?

Posted: Sat Aug 27, 2016 9:37 pm
by ArthurGPym
Intenté usar dijkstra pero no logro hacerlo funcionar de forma eficiente/correcta.

Re: 1766 - Full Tank?

Posted: Wed Aug 31, 2016 12:37 pm
by 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

Re: 1766 - Full Tank?

Posted: Mon Sep 05, 2016 4:36 pm
by 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

Re: 1766 - Full Tank?

Posted: Mon Sep 05, 2016 11:42 pm
by ArthurGPym
Gracias. Voy a probar lo que me dicen y ver si me funciona.