Sto impazzendo, ho provato a fare tutto con una bfs (aggiungendo due elementi alla coda, nel caso si usa l’autobus e nel caso si va a piedi), ho provato con una dfs ma faccio 0/100 perché va in timeout / troppa memoria…
Mi pare di aver provato pure con un dijkstra qualche tempo fa, infatti ero riuscito ad ottenere 23 punti.
Non ho più la minima idea di come provare a risolverlo.
Mi sono fatto aiutare un bel po’ per risolvere questo problema. Ti do alcuni indizi per risolverlo.
Il primo indizio è che, dato un sottografo dove gli archi il cui numero di volontarie è maggiore di un valore V, se è irrisolvibile allora anche un sottografo di questo sottografo sarà irrisolvibile.
Il problema allora si traduce in: “qual è il valore minimo di V affinché la funzione appena creata dia esito positivo?”
Okay, grazie mille, adesso non ricevo più alcun timeout però ho un bel po’ di output non corretti.
Ciò che faccio io è fare una DFS con cui vedo se è possibile raggiungere E (la destinazione) incontrando al massimo V volontarie.
Faccio una ricerca binaria per V, minimo 0 massimo 1000001 (siccome il massimo di volontarie è un milione) e il più piccolo valore possibile è la soluzione.
Se non è possibile -1.
Sbaglio o è così?
In caso ho davvero bisogno di aiuto nel codice, ieri ho perso un pomeriggio.
Hai compreso l’idea di fondo, molto bene.
Ma perché usi una DFS?
Ricordati che questo è un problema di ottimizzazione, di conseguenza forse ti converrebbe vedere il grafo come una ricerca di cammino minimo. Ma minimo di cosa? [spoiler]Del tempo impiegato.
La cosa più semplice è implementare Dijkstra considerando come “costo” il tempo impiegato. Un percorso allora si dirà possibile se esiste e il costo minimo è inferiore o uguale a T.
Lemma (a cui ti lascio l’onere della dimostrazione): se un percorso può essere risolto usando al massimo V_a volontarie con tempo massimo T_a, allora è risolvibile anche con al massimo V_b volontarie (V_a < V_b) in tempo minimo T_b \leq T_a
[/spoiler]
Se hai qualche dubbio, pastebin è tuo amico.
Ho provato a implementare il dijkstra (che penso di aver fatto bene), però ottengo gli stessi risultati… è da una ventina di sottoposizioni che ottengo gli stessi output non corretti, ci sto perdendo le speranze, temo e spero che il bug sia da qualche altra parte:
Ho messo qualche commento, spero si capisca.
Grazie ancora.
Perché usare una matrice solved? Credo sia un retaggio della DFS di prima, perché con Dijkstra non ne hai bisogno, anzi ti fa sbagliare in alcuni casi, ovvero quando stai riconsiderando uno stesso percorso per il quale hai pagato lo stesso numero di biglietti ma che potrebbe essere conveniente “riattraversare” perché magari hai impiegato un tempo minore rispetto all’ultima volta per arrivarci.
Solved la usavo per non riaggiungere nodi già risolti alla coda, comunque l’ho tolta e adesso ottengo sempre 0/100 ma alcuni output non corretti sono diventati timeout/errori 11.