Link problema - link
Secondo me, il problema può essere risolto da una struttura dati, che mostra come ogni numero è connesso a un altro e tramite la ricorsione trovi il valore più piccolo possibile. Ma la mia domanda è: quale struttura dati (più efficiente) può contenere / rappresentare tali dati? Inoltre, c'è un modo migliore (più veloce) per risolvere questo problema.
Grazie
Il problema è equivalente al problema del percorso più breve in un grafico, in cui i vertici sono dati dal primo e terzo numero di ciascuna delle tue triple, un margine è dato da una tripla "connessione" di due vertici, e il peso del bordo è dato dal secondo numero di ciascuna tripla. Può essere risolto in modo efficiente, ad esempio, tramite l'algoritmo di Dijkstra . L'articolo di Wikipedia elenca alcune strutture di dati dell'heap per grafici che potrebbero essere appropriati per questo algoritmo purché il grafico sia "sparse".
array multidimensionale, possiamo anche chiamarlo matrice.
crea una matrice nxn dimentional (diciamo A) - dove n è il numero del nodo nel grafico.
quando il nodo i e j è collegato, imposta A[i][j] su 1 altro su 0.
Leggi altre domande sui tag c++ data-structures algorithms