Ciao a tutti, stavo cercando di risolvere Scale di Hogwarts, ma non riesco a trovare l’errore in un algoritmo che mi sembra corretto.
L’idea è di usare Dijkstra usando il tempo impiegato come distanza (dato che il tempo è la quantità che vogliamo minimizzare). Gli archi nella lista di adiacenza sono formati da una coppia, in cui il primo elemento è un intero (arco di arrivo) e il secondo è una coppia di interi che rappresentano il tempo di comparsa e scomparsa dell’arco. La base dell’algoritmo è che, arrivati a un certo nodo u ad un tempo t, possiamo controllare tra tutti i nodi adiacenti quali possono essere raggiunti (cioè quali scompaiono dopo t) e aggiungere questi alla coda di priorità con tempo t+1 se l’arco è già comparso al tempo t, altrimenti con tempo uguale al tempo di comparsa dell’arco.
Alla fine se dist[N-1] è INF ritorno -1, altrimenti dist[N-1] è il numero che sto cercando.
Ecco il codice, grazie!
for (auto i : graph[head.curr])
if (i.second.second > head.dist)
if (max(i.second.first, dist[head.curr] + 1) < dist[i.first])
Premesso che non ricordo bene il testo, nel primo if non serve un >= al posto di un >?
Ho messo > perché se una scala scompare al tempo t e io la raggiungo al tempo t, non posso usarla nel minuto che va da t a t+1. In ogni caso cambiare il > con un >= non cambia nulla, tutti i testcase sbagliati continuano ad essere sbagliati e quelli giusti continuano ad essere giusti…
Ciao, ho letto velocemente il tuo codice; noto che usi più o meno le stesse strutture dati che ho usato io, ma non ho il tempo di leggerlo per bene e dirti dove sbagli, ti metto qui il mio da 100/100 e se hai voglia guardatelo tu:
Hogwarts.cpp
Grazie per l’aiuto! Mi sono accorto, ad esempio, che nel caso in cui la scala compare dopo dell’istante in cui sono sulla sala, io arriverò nella prossima sala nel tempo i.second.first+1 e non i.second.first. Però il problema rimane e non riesco davvero a capire dove sia l’errore… Ho anche provato ad usare l’implementazione di Dijkstra del Competitive Programming, non sapendo se fosse in qualche modo legata, ecco il nuovo codice (che dovrebbe essere praticamente uguale al precedente a meno dell’errore e dell’implementazione): hogwarts.cpp
Mi sono appena accorto di aver messo la condizione sbagliata nell’if e l’algoritmo inseriva altri archi solamente se erano già scomparsi al tempo t e non il contrario 
Grazie ancora per l’aiuto ragazzi, 100/100 ora!