Instradamento della Mucca (Bronzo)#11185
Stanca del freddo inverno nella sua fattoria, Bessie la mucca decide di volare verso una destinazione più calda per le vacanze. Sfortunatamente, scopre che solo una compagnia aerea, Air Bovinia, è disposta a vendere biglietti alle mucche, e che questi biglietti sono in qualche modo complicati.
Air Bovinia possiede aerei, ciascuno dei quali opera su una specifica "rotta" composta da due o più città. Per esempio, un aereo potrebbe seguire una rotta che inizia dalla città , poi vola verso la città , poi verso la città , e infine verso la città . Nessuna città compare più di una volta su una rotta.
Se Bessie sceglie di utilizzare una rotta, può salire sull'aereo in qualsiasi città lungo la rotta e scendere in qualsiasi città che compaia successivamente sulla rotta. Non è obbligata a salire dalla prima città né a scendere all'ultima città. Ogni rotta ha un costo fisso, che Bessie deve pagare se utilizza una qualsiasi parte della rotta, indipendentemente da quante città visiti lungo di essa.
Bessie vorrebbe trovare il modo più economico per viaggiare dalla sua fattoria (nella città ) alla sua destinazione tropicale (città ). Poiché non vuole avere a che fare con un itinerario complicato, vuole utilizzare solamente una singola rotta. Aiutala a determinare il costo minimo che deve pagare.
La prima riga contiene tre interi A, B, n~(1 \le n \le 500).
Le successive righe descrivono le rotte disponibili, con due righe per ciascuna rotta.
La prima riga contiene il costo di utilizzo della rotta (un intero compreso tra e ) e il numero di città lungo la rotta (un intero compreso tra e ).
La seconda riga contiene un elenco delle città nell'ordine lungo la rotta. Ogni città è identificata da un intero compreso tra e .
Stampa il costo minimo di una singola rotta che Bessie può utilizzare per viaggiare dalla città alla città . Se non esiste tale rotta, stampa .
Sebbene esista una soluzione più economica con due rotte (usando la rotta per viaggiare dalla città alla città , e poi la rotta per viaggiare dalla città alla città ), a Bessie è permesso utilizzare solo una singola rotta. Pertanto, deve usare la rotta , a un costo di .
Esempio 1