Salve ragazzi, scrivo per chiedervi dei suggerimenti su come muovervi per questo esercizio in C.
Ho un grafo non orientato e pesato in cui il peso descrive la lunghezza di una strada.
Per ogni nodo del grafo c'è un attributo che indica l'altezza della strada oltre al numero che riconosce il nodo stesso.
Il dilemma è che devo trovare un percorso minimo per raggiungere l'ultimo nodo del grafo e questo percorso deve prevedere prima un cammino tutto in salita e poi uno tutto in discesa. Quindi se sono in un nodo di altezza 20(per esempio) posso continuare a salire in nodi con altezza >20 oppure iniziare la discesa e a quel punto ogni altezza deve essere minore del successivo. Infine,la complessità deve non deve essere maggiore O(n+m) con n numero di vertici ed m numero di archi.
Sapete darmi qualche dritta?