Salve a tutti, per necessità, dato il tipo di input, ho un grafo derivato da una tabella hash. La tabella è implementata mediante liste di collisione, gli oggetti memorizzati nella tabella sono i Vertici del grafo i quali contengono i campi string nome (usato come chiave) ed una lista di Vertici* contenente i vertici adiacenti (implementata mediante un vettore).

Al crescere dell'input (circa sul milione di vertici) il tempo di esecuzione raggiunge i decimi di secondo, cosa che vorrei proprio evitare per il fine del programma. In particolare ho notato che la popolazione della tabella mi richiede veramente troppo tempo, vi posto di seguito i metodi usati:

codice:
TABELLA HASH
void inserisci (const string& s1, const string& s2, unsigned int distanza)
{
	Vertice* v1 = searchAndInsert (s1);
	Vertice* v2 = searchAndInsert (s2);

	v1->inserisciAdiacente (*v2, distanza);
	v2->inserisciAdiacente (*v1, distanza);
}

Vertice* searchAndInsert (const string& s) //Se è già presente lo ritorna, altrimenti lo inserisce alla fine e ritorna l'ultimo elemento inserito
{
	unsigned int i = FunzioneHash (s) % dim;

	for (list<Vertice>::iterator it = tabella[i].begin(); it != tabella[i].end (); it++)
		if (it->getNome () == s)
			return &(*it);

	tabella[i].push_back (Vertice (s));
	++numElementi;
	return &tabella[i].back ();
}

VERTICE
void inserisciAdiacente (const Vertice& v)
{
	lista[i] = &v; //dove lista è un vettore dinamico implementato da me
}
Mi rivolgo a voi per qualche consiglio su come poter migliorare il tutto..