Instradamento della Mucca (Bronzo)#11185

Instradamento della Mucca (Bronzo) (Editoriale)

Ogni percorso definisce una sequenza direzionata di città. Poiché Bessie vuole utilizzare un solo percorso, per ciascun percorso è sufficiente verificare:

la città $A$ compare prima della città $B$ ?

Se questa condizione è soddisfatta, Bessie può usare questo percorso e pagare il suo costo fisso. Tra tutti i percorsi adatti, bisogna trovare il percorso con il costo minimo.

Esempio

Nell'esempio ci sono $3$ percorsi:

$3 \to 2 \to 1$ 3 \to 2 \to 1;
$2 \to 1 \to 4 \to 3$ 2 \to 1 \to 4 \to 3;
$4 \to 1 \to 7 \to 8 \to 2$ 4 \to 1 \to 7 \to 8 \to 2;

Poiché $A = 1$ A = 1 e $B = 2$ B = 2, Bessie può usare solo il terzo percorso: la città $1$ compare in esso prima della città $2$ . Il costo di questo percorso è pari a $8$ .

Implementazione dell'algoritmo

Dichiariamo una costante $I N F$ .

#define INF 1000000000

Leggiamo i dati in ingresso.

scanf("%d %d %d", &a, &b, &n);

Inizializziamo la variabile $r es$ , in cui conserveremo la risposta.

res = INF;

Scorriamo gli $n$ percorsi.

for (i = 0; i < n; i++)
{

Leggiamo il costo del percorso $cos t$ e il numero di città $sz$ su questo percorso.

  scanf("%d %d", &cost, &sz);

La variabile $f l a g$ contiene $f a l se$ , se la città $А$ non è ancora comparsa sul percorso corrente.

  flag = false;

Leggiamo in sequenza le città sul percorso corrente.

  for (j = 0; j < sz; j++)
  {
    scanf("%d", &city);

Se compare la città $А$ , impostiamo $f l a g = t r u e$ flag = true.

    if (city == a) flag = true;

Se compare la città $B$ , e prima di essa sul percorso è già comparsa la città $А (f l a g = t r u e)$ А~(flag = true), allora Bessie può usare questo percorso, pagando il suo costo $cos t$ .

Se ci sono più percorsi adatti, scegliamo il percorso con il costo minimo.

    if (flag && city == b) res = min(res, cost);
  }
}

Dopo aver elaborato tutti i percorsi, stampiamo la risposta.

if (res == INF)
  printf("-1\n");
else
  printf("%d\n", res);