SoloCodigo

Necesito diseñar un software en C y necesito ayuda ya que no se como programar grafos dirigidos, solo se diseñar listas simples, enlazadas, circulares, pilas y colas, ojalaque esos conocimientos me sirvan de algo, pero el problema radica en que no se como hacerlo ya que necesito usar grafos, a continuacion expongo el problema, si alguien me puede ayudar por favor enviarme un email:

Un empresa de transportes atiende a un numero de ciudades, las que deben estar conectadas entre si por buses y aviones. Si existe un vuele de la ciudad i a la ciudad j, tambien existe un bus de la ciudad i a la j y de la j a la i, pero no necesariamente existe un avion de la ciudad j a la i.
Los vuelos pueden tener escalas.
1.- Diseñar un grafo que contenga las ciudades y que ademas tenga:

10.000 ciudades que pueden ser generadas en forma aleatoria.

Mediante una matriz de adyacencia indica la relacion entre los vertices, que debe ser creada en              forma aleatoria.

En base a la informacion generada en los puntos anteriores etiquete entre 1 y 100 los costos de los arcos. Todos los costos entre [1,500] equivalen a viajes en bus, los superiores a 500 equivalen a viajes en avion.

Guarde su grafo en un archivo llamado "grafo.txt" de la siguiente forma :
Vertice1,Vertice2, (ini,fin)
Eje
1,2(2,1) indicara 2------->1.

2.- El programa ademas debe tener:

Una funcion que tome el archivo "grafo.txt" y cree una lista de adyacencia y guarde los resultados en un archivo llamado "lista.txt" que debe tener el siguiente formato:
Nodo1>Nodo2,Nodo3...
Nodo2>Nodo5,Nodo5...

El programa debe solicitar indicar el punto de origen y de partida, en base a esto el programa debe indicar la ruta mas economica, indicando todas las escalas si es que las hay, indicando si se usa bus, avion, ambas y cuanto de cada una.
Utilice el algoritmo Dijkstra.

POR FAVOR AYUDA SOLO EN ENTENDER COMO SE HACE.

SE AGRACEDE AYUDA.