Perros callejeros és una pel·lícula de 1977 dirigida per José Antonio de la Loma i protagonitzada per Ángel Fernández Franco, alias El Torete que es basa en la vida de Juan José Moreno Cuenca alias El Vaquilla.

El Vaquilla i el Torete en la vida real eren dos coneguts delinqüents dels entorns de Barcelona. Experts en el robatori de cotxes, els feien servir per fugir dels atracaments i, molt sovint, acabaven en espectaculars persecucions de la policia on habitualment els policies no sortien gaire ben parats.

Farts d'aquesta situació, amb el temps, la policia va estudiar el patró d'actuació dels delinqüents i era capaç de predir les possibles rutes de fugida que havien preparat els delinqüents, donat que sempre era alguna de les rutes més ràpides des del lloc del delicte fins al seu amagatall. D'aquesta manera, muntaven dispositius en diferents carrers i els esperaven allà per detenir-los. Que no anessin a buscar-los directament al seu amagatall és un tema que potser tractarem en algun altre problema.

Els delinqüents, que no tenien un pèl de tontos, s'ho veien venir i canviaven la seva ruta fent servir la ruta alternativa més ràpida que no passava per cap carrer de cap ruta inicial més ràpida. Per evitar que els enxampessin al mateix carrer on cometien l'atracament van optar per fer-los només a les cruïlles, d'aquesta manera sempre tindrien més d'una via d'escapament.

Entrada

L'entrada té diferents casos de prova on cadascú representa un atracament diferent.

La primera línia del cas conté dos números: I (entre 1 i 10.000) i C (entre 1 i 100.000) que indiquen el nombre d'interseccions i el nombre de carrers de la ciutat. Seguidament, venen C línies amb la informació de cada carrer: dos números (entre 1 i I) que indiquen les interseccions que uneix el carrer i un tercer número que indica el temps que es triga a travessar el carrer.

En cada cas de prova, l'atracament es comet a la primera intersecció 1 i l'amagatall es troba a la darrera intersecció. Sempre hi ha almenys un camí que porta des de la primera a la darrera intersecció. No cal dir que en una fugida no es respecta cap senyal de trànsit i, per tant, pels delinqüents tots els carrers són de doble sentit.

Sortida

Per a cada cas cal indicar el temps que trigaran a arribar al seu amagatall evitant tots els carrers que haguessin fet servir en el seu pla inicial. Com que els controls policials es munten als carrers i no a les cruïlles, no hi ha cap problema per passar per alguna de les cruïlles del pla original. En cas que no es pugui arribar a l'amagatall sense passar per cap carrer on pot estar el dispositiu policial cal escriure CAPTURA.

Exemple d'Entrada

4 4 
1 2 1
2 3 1
3 4 1
1 4 5
4 4 
1 2 1
2 3 1
3 4 1
1 3 5
4 4 
1 2 1
2 3 1
3 4 1
1 4 3

Exemple de Sortida

5
CAPTURA
CAPTURA