Salve ragazzi, avrei bisogno di aiuto con questo problema.
Totalizza solamente 30/100 e non passa i test case 1,4,5,6,7,8,9 con output sbagliato (tranne 8 e 9 in cui va in time out). L’algoritmo consiste nell’applicare dijkstra ad ogni arco, con partenza da un nodo e arrivo nell’altro, evitando di passare sull’arco corrente, ed è praticamente uguale alla soluzione presentata nel booklet di bugatti.
Ecco il mio codice:
Un problema potrebbe essere il fatto che tu ti guardi indietro solo per evitare di reinserire nella queue l’arco di partenza ma in realtà dovresti farlo ogni volta che fai una visita a un nodo tendendoti conto dell’arco da cui provieni(in questo modo lo velocizzi un sacco).
Si, in effetti, però non credo sia quello a causare l’ouput sbagliato.
In realtà adesso che ci penso meglio non lo velocizzi di molto dato che vedi un nodo solo 1 volta xD, l’errore non penso sia nel modo in cui hai implementato dijkstra…
Ok, ho risolto implementando una ricorsiva. Ora prendo 100/100.