Dev - C++ - Problema con grafos

hola quetal estoy haciendo un programa con grafos mas especifico una ruta en grafos y cada vertice del grafo tiene 5 datos como minimo nombre,tiempo,etc.. y nose en cual implementar ,matriz de adyacencia o lista de adyacencia y mis dudas son: saber si la matriz puede guardar mas de un dato en un fila y columna especifica o si en un programa se puede crear varias listas ligadas una para cada vertice.

:-( ayudenme.. pliz muchachos.