2714 - Food and Medicine

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2714 - Food and Medicine

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 2714 - Food and Medicine

Post by ArthurGPym » 2 years ago

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

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: 2714 - Food and Medicine

Post by isaac » 2 years ago

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!!.

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 2714 - Food and Medicine

Post by ArthurGPym » 2 years ago

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

Post Reply

Return to “Problem set”