Page 1 of 1

2714 - Food and Medicine

Posted: Sat Mar 01, 2014 3:07 pm
by ymondelo20

Re: 2714 - Food and Medicine

Posted: Sat Oct 08, 2016 1:07 am
by ArthurGPym
Hola, estoy intentando resolver el problema con floyd warshall pero me dice "Wrong Answer". Estuve un rato largo buscando que esta mal pero no lo encuentro. Les muestro el codigo que me da error:
► Show Spoiler


Me podrian ayudar? saludos

Re: 2714 - Food and Medicine

Posted: Sat Oct 08, 2016 12:46 pm
by isaac
Tengo algunas dudas respecto a tu código.
1- Cuando creas tu matriz de adyacencia...¿estas seguro que todos los elementos se inicializan en cero??
2- Cuando lees los caminos y pesos en la entrada...¿tienes la garantía de que no se van a repetir? Podrían darte la siguiente entrada:
2 1 1
1 2 3

y tu programa daría WA. En el problema no te garantizan eso y no lo tienes en cuenta. A lo mejor puede ser alguna de estas dos opciones.

Otro detalle...en el código del floyd, puedes hacerlo más eficiente. Recuerda que siempre vas a actualizar ad[j] si ad[k] + ad[k][j] es menor, cierto?? Entonces si alguno de estos dos es 10^9, que es el valor que le pusiste como marcador, podrías poner una condicion que verifique esto entre el segundo y el tercer for, de modo que no se ejecute un recorrido innecesario puesto que si [k] tiene 10^9, [j] nunca se va a actualizar. Saludos!!.

Re: 2714 - Food and Medicine

Posted: Sat Oct 08, 2016 1:02 pm
by ArthurGPym
hola, gracias por responder. Con respecto a las dudas:

1) java por defecto inicializa toda matriz o array de enteros en cero.
2) es verdad, puede ser que se repitan, en el enunciado del problema no lo especifica. Voy a revisar eso

Saludos