Buonasera, stavo provando a risolvere Barbablù e avevo intenzione di usare Dijkstra.
Volevo però chiedervi come poter tenere conto anche dell’ossigeno durante l’esecuzione dell’algoritmo.
Grazie
Per ogni nodo i mi salvo, attraverso un flag, se quel nodo è o meno una camera d’aria.
Quando applichi Dijkstra devi fare in modo che se
- il nodo i e il nodo j sono camere d’aria allora controlli che l’arco sia minore di 20
- il nodo i o il nodo j (o tutt’e due) non sono una camera d’aria devi salvarti in una variabile contenuta nel nodo di arrivo il valore che poi verrà confrontato non appena il sub arriverà ad una camera d’aria.
Mi spiego meglio:
Se il sub si trova in una camera d’aria e il nodo accanto non lo è, bisogna salvare il valore di quell’arco. Dopo di che il sub continuando il suo viaggio da quel nodo, se l’arco più vicino è una camera d’aria bisogna controllare che il tragitto che ha percorso dal nodo iniziale fino alla camera d’aria sia minore di 20.
Potresti più semplicemente passare alla priority queue il valore dell’ aria ancora disponibile. Quando devi pushare nella priority controlli se l’ aria disponibile è abbastanza per percorrere l’ arco.