Instradamento delle mucche (Argento)

Stanca del freddo clima invernale nella sua fattoria, la mucca Bessie sta pianificando di andare in vacanza in un luogo più caldo. Sfortunatamente, scopre che solo una compagnia aerea, Air Bovinia, è disposta a vendere biglietti alle mucche, e questi biglietti sono organizzati in modo piuttosto complicato.

Air Bovinia possiede $n$ aerei, ciascuno dei quali vola secondo una determinata "rotta", composta da due o più città. Ad esempio, uno degli aerei potrebbe seguire una rotta che inizia nella città $1$, poi passa per la città $5$, poi per la città $2$ e infine arriva nella città $8$. Nessuna città compare più di una volta nella stessa rotta.

Se Bessie decide di utilizzare una rotta, può salire sull'aereo in qualsiasi città di quella rotta e poi scendere in qualsiasi città che si trovi più avanti lungo la rotta. Non è obbligata a salire nella prima città della rotta né a scendere nell'ultima. Ogni rotta ha un costo fisso che Bessie deve pagare ogni volta che utilizza una qualsiasi parte di quella rotta, indipendentemente dal numero di città che attraversa.

Se Bessie utilizza la stessa rotta più volte durante il suo viaggio (cioè lascia la rotta e poi, in un momento successivo, vi ritorna e la utilizza di nuovo partendo da una città diversa), deve pagare il costo di quella rotta ogni volta.

Bessie vuole trovare il modo più economico per arrivare dalla sua fattoria, situata nella città $A$, alla sua destinazione tropicale, situata nella città $B$. Aiutala a determinare sia il costo totale minimo del viaggio, sia, tra tutti i percorsi con questo costo minimo, il numero minimo di voli distinti che deve effettuare.