Dopo aver visto la soluzione del problema 4 delle Quaranterry (provato in gara ma senza risolverlo), volevo risolvere un problema on una idea simile.
Credo di aver capito la soluzione, aiutandomi anche con alcuni post vecchi sullo stesso problema, ma non sono riuscito a capire che cosa sto sbagliando. Il mio codice fa solo i casi di esempio, il subtask 3 giusto (8/100) e qualche altro testcase corretto.
Quello che sto facendo è di cercare la soluzione con un binary search (da 0 a 1e9+1) controllando ogni volta che, calcolato il tempo minimo per raggiungere E con dijkstra applicato ad un grafo con K+1 ‘livelli’, questo sia minore uguale di T, e ritorno quindi il minimo V valido, se il binary search esce con 1e9+1 invece ritorno -1.
Sono quasi 2 ore che controllo il codice e non riesco a capire che cosa sto sbagliando.
C’è un errore nella mia soluzione?
Questo è il codice che ho dato
got.zip (824 Byte)
Ciao! Il problema di risposta errata è dato solo dal return m alla fine della funzione, infatti non è detto che m sia sempre valido. Per come hai implementato la b_search, dato che quando m è valido y = m-1, hai che y+1 è sempre valido ed è la risposta cercata (quando è possibile).
Rimane comunque un problema di tempo in un paio di testcases (almeno nella sottoposizione che ho fatto io 
) ma anche questo è facilmente risolvibile: basta pensare al fatto che M\leq5000, quindi puoi ridurre il problema ad una binary search su M valori. Spero di aver risolto.
Grazie mille per l’aiuto! Il tuo accorgimento mi ha risolto la cosa.
Grazie anche per il suggerimento di ottimizzazione del programma, a quello non avevo ancora pensato poichè la mia soluzione già non funzionava.