[C++] Brisbane

Nel 2013, le IOI si svolgeranno a Brisbane (in Australia). La rappresentativa italiana
ha  già  iniziato  a  studiare  la  città,  per  capire  cosa  ci  sia  di  interessante  da  vedere,  e
come  ci  si  possa  spostare  nella  giornata  libera  successiva  alla  seconda  gara  delle
Olimpiadi. L’offerta di trasporto pubblico a Brisbane è abbastanza variegata: ci sono
due linee di bus, di cui una gratuita che gira intorno alla città, e due linee di traghetti
che fermano in diversi punti del fiume Brisbane, che taglia la città in due; per quello
che  riguarda  i  prezzi,  esiste  un  abbonamento  giornaliero  a  tutti  i  trasporti  pubblici,
bus e traghetti insieme, oppure è possibile prendere un più economico abbonamento
giornaliero ai soli traghetti, o un ancor più economico abbonamento ai soli bus.
La  squadra  italiana  vorrà  visitare  il  maggior  numero  di  attrazioni  possibile  e  per
questo  motivo  Monica,  la  responsabile  dell’organizzazione,  ha  deciso  di  cercare  un
buon  compromesso  tra  il  prezzo  dei  biglietti  e  le  attrazioni  che  sarà  possibile
raggiungere  partendo  dall’hotel.  Data  una  lista  di  attrazioni  e  la  mappa  dei
collegamenti delle diverse linee del trasporto pubblico, il vostro compito è quello di
aiutare Monica a capire quante attrazioni sono raggiungibili per ogni possibile scelta
dei biglietti per i trasporti pubblici.

Per esempio, possiamo fare riferimento alla figura qui a destra, dove ad ogni fermata è
associato un cerchio (o un quadrato nel caso di luogo di attrazione) e i collegamenti
sono:
tratteggiati – collegamenti gratuiti (bus gratuiti e brevi percorsi a piedi);
rossi – bus a pagamento;
gialli – traghetto.
Il punto di partenza della rappresentativa italiana è la fermata numero 0; le attrazioni
da vedere sono quelle rappresentate con un quadrato, numerate rispettivamente 8, 12,
15, 22 e 28. Come si può vedere, spostandosi con i mezzi gratuiti si raggiungono solo
due  attrazioni  (la  numero  8  e  la  numero  14);  comprando  il  biglietto  del  bus  si
raggiungono  tutte  le  attrazioni;  comprando  il  biglietto  del  traghetto  si  raggiungono,
oltre alla 8 e la 14, anche la 12 e la 15 per un totale di quattro attrazioni. Il biglietto
combinato, in questo caso, raggiunge tutte le attrazioni.

Dati di input
Il file input.txt è composto da 1+A+Mg+Mb+Mt righe. La prima riga contiene cinque
interi positivi separati da uno spazio, che rappresentano il numero N delle fermate, il
numero  A  di  attrazioni,  il  numero  Mg  dei  collegamenti  gratuiti,  il  numero  Mb  dei
collegamenti  via  bus  e  il  numero  Mt dei collegamenti via traghetto. Ogni fermata è
rappresentata da un intero compreso tra 0 e N­1. Le successive A righe  contengono
ognuna  una  fermata  (un  intero  compreso  tra  0  e  N­1)  corrispondente  ad  una  delle
attrazioni  che  la  rappresentativa  italiana  può  visitare.  Ognuna  delle  successive
Mg+Mb+Mt righe contiene un collegamento del trasporto pubblico, rappresentato da
due interi positivi: le fermate collegate. Le prime Mg righe contengono i collegamenti
gratuiti  (bus  gratuiti  e  brevi  percorsi  a  piedi),  poi  le  successive  Mb  contengono  i
collegamenti  del  bus  a  pagamento  e  infine  le  ultime  Mt  righe  contengono  i
collegamenti  dei  traghetti.  Il  punto  di  partenza  della  rappresentativa  italiana  è  la
sempre la fermata numero 0.
Dati di output
Il file output.txt è composto da 4 righe contenenti ognuna un intero non negativo,
rispettivamente, il numero di attrazioni raggiungibili:
1.  senza comprare biglietti (solo con mezzi gratis);
2.  comprando solo il biglietto giornaliero dei bus;
3.  comprando solo il biglietto giornaliero dei traghetti;
4.  comprando entrambe le tipologie di biglietti.

Assunzioni
• 2 ≤ N ≤ 1000
• N ≤ Mg+Mb+Mt ≤ 10000

Esempi di input/output

 

Qui bisogna scrivere le città nei grafi {gratis, col bus, col treno, tutti} e contare per ogni grafo quante tappe si possono raggiungere.