2714 - Food and Medicine

[ymondelo20]

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

[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

import java.util.Arrays;
import java.util.Scanner;


public class Main100{
static int v,e;
static int AdjMat[][];

public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt(), q;

while (t-- > 0) {
v = in.nextInt();
e = in.nextInt();
AdjMat = new int[v][v];
for (int i=0; i<v; i++) {
for (int j=0; j<v; j++) {
if (i!=j)
AdjMat[j] = 1000000000;
}
}
for (int i=0,a,b,d; i<e; i++) {
a = in.nextInt()-1;
b = in.nextInt()-1;
d = in.nextInt();
AdjMat[a] = AdjMat[a] = d;
}
q = in.nextInt();
fw ();
for (int i=0,a,b; i<q; i++) {
a = in.nextInt()-1;
b = in.nextInt()-1;
System.out.println (AdjMat[a]==1000000000? -1:AdjMat[a]);
}
if (t>0)
System.out.println ();
}
}

static void fw () {
for (int k = 0; k < v; k++)
for (int i = 0; i < v; i++)
for (int j = 0; j < v; j++)
AdjMat[j] = Math.min(AdjMat[j], AdjMat[k] + AdjMat[k][j]);
}
}

Me podrian ayudar? saludos

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

[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